leetcode1--two sum

leetcode1--two sum

题目

题目如下


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].

解答

这个最容易想到的就是暴力search,直接两个for判断就可以了,但是这样行是行,但是效率不高,这个里面有个很强的假设,即刚好有一个解,

高效的方式是o(n)就可以做到,我现在思维上有个缺点,总是会把o(n)当成是遍历一次,其实o(n)可以遍历好几次,这种把多层for拆开来做的基本上都是采用的这种想法,即多次遍历,注意不是多重遍历。

这样这个题可能先遍历一次,以值为key,以index作为value来建立一个字典, 然后再遍历一次,对于nums[i]这个数,来看’target-nums[i]’有没有在上一步的字典中有,注意这时候第二个index应该是大于第一个才可以, 之所以第二index要大于第一个是因为这种情况,即输入是【3,3】target是6. 如果不大于i的话,[0,0]也是解.其实大于i也比较自然,因为就是要选出两个不同的数.

代码如下

class Solution(object):
    
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        
        dic = dict(zip(nums, range(len(nums))))
        for i in range(len(nums)):
            j = dic.get(target-nums[i], -1)
            if j >-1 and i < j:
                return [i,j]
    

我刚开始是这样写的,遍历了两次,第一次是建立字典,第二次才查找,但是完全可以边建立字典边进行查找.

dic = {}
        for i, x in enumerate(nums):
            dic[x] = i
        # 有重复的也没有事儿
        
        for i, x in enumerate(nums):
            if (target-x) in dic and dic[target-x] > i:
                return [i, dic[target-x]]
            
        return None
        

其实也可以这样写,即边建立字典边找,这在第560题那里也用到了.

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dic = {}        
        for i, x in enumerate(nums):
            
            if target-x in dic:
                return [dic[target-x], i]
                
            if x not in dic:
                dic[x] = i
         

用c++的话,需要用到unordered_map

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //申请一个对象
        unordered_map<int, int> m;
        vector<int> res;
        for(int i=0;i<nums.size();i++){
            m[nums[i]] = i;
        }
        for(int i=0;i<nums.size();i++){
            int t=target-nums[i];
            if(m.count(t) && m[t] !=i){
                res.push_back(i);
                res.push_back(m[t]);
                break;
            }
        }
        
        return res;
    }
};

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦