[Array] 001 Two Sum

• 分类：Array

• 考察知识点：Array(数组遍历) HashMap

• 最优解时间复杂度：O(n)

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

这道题最优的解法就是创建一个HashMap,在Python中我们称为Dictionary(主要我用Python,更加习惯用Python来讲解内容),边遍历边存储原来的那些内容到一个Dictionary里供后面搜索。

还是拿[2,7,11,15]这个list举例：

代码：

最优解法:

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        # 确定边界
        if len(nums)<2:
            return [-1,-1]
        
        # O(n)解法
        num_dict={}
        for i,n in enumerate(nums):
            if (target-n) in num_dict:
                return [num_dict[target-n],i]
            else:
                num_dict[n]=i

讨论：

1.这个题目我一开始是想用双循环去解的也就是一个循环套一个循环,感觉这个是最普通最大众的解法，但是时间复杂度太高了，为O(n^2)
2.后来我想过用另外一个方法去解也是一个循环,但是这个方法并不好，因为Python已经“暗中”遍历了好多遍了

        for n in nums:
            if (target-n) in nums:
            #Python在这里暗中会遍历一遍
                return [nums.index(target-n),nums.index(n)]
                #这个index的函数也会让Python去暗中区遍历

3.另外上述方法不好的一个地方是，题目里讲了“may not use the same element twice”，如果要重新检测的话又要用到切片什么的就更加麻烦了。

WechatIMG1573.jpeg

最终我们交上第一题的完美答卷！Perfect Start!