Leetcode 题解: L1 Two Sum

title: 'Leetcode 题解: L1 Two Sum'
comments: true #是否可评论
toc: true #是否显示文章目录
categories: Leetcode
tag:
- Algorithm
- DataStruct

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

查找第二个数的时候用二分的方法，所以要另外开辟一个空间，用来保存原始数据的位置。

//C++
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> t = nums;
        sort(nums.begin(), nums.end());
        
        vector<int> res;
        for (int i=0; i<nums.size()-1; ++i)
        {
            int sp = i+1;
            int ep = nums.size()-1;
            while (sp<=ep)
            {
                int mid =(sp+ep)/2;
                if (nums[mid]+nums[i]==target)
                {
                    res.push_back(nums[mid]);
                    res.push_back(nums[i]);
                    break;
                }
                
                if (nums[mid]<target-nums[i])
                    sp = mid+1;
                else
                    ep = mid-1;
            }   
        }
        
        for (int i=0; i<t.size(); ++i)
        {
            if (t[i]==res[0])
            {
                res[0] = i;
                break;
            }
        }       
        for (int i=0; i<t.size(); ++i)
        {
        if (t[i]==res[1] && i!=res[0])
            {
                res[1] = i;
                break;
            }
        }
        return res;
    }
};

#python

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        tnums = []
        for i in range(len(nums)):
            tnums.append(nums[i])
        nums.sort()
        Lval = []
        for i in range(len(nums)-1):
            sp=i+1
            ep = len(nums) - 1
            while sp<=ep:
                mid = int(sp + (ep - sp)/2)
                #mid = int(mid)
                if (nums[mid] + nums[i]) ==target:
                    Lval =  [i, mid]
                    break
                elif nums[mid]+nums[i] > target:
                    ep = mid - 1
                else:
                    sp = mid + 1
            if len(Lval)==2:
                break
        #print (",,,,", Lval[0], Lval[1])
        ret = []
        for  i in range (len(tnums)):
            #print(tnums[i])
            
            if tnums[i]==nums[Lval[0]]:
                #print("000", i, tnums[i], nums[Lval[0]])
                ret.append(i)
                continue
            if tnums[i]==nums[Lval[1]]:
                #print("1", i, tnums[i], nums[Lval[1]])
                ret.append(i)
            if len(ret)==2:
                break
            
        return ret

个人博客：www.junxing.tech，欢迎访问。