1.2Sum

2019-03-28

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:

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

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

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def twoSum(self, nums, target):

        # 相当于哈希表
        dic = {}
        rList = []
        valueList = []

        # 我们要求的是元素的索引，即Hash表的关键字，所以我们把数组元素作为dict的key
        # 而把数组元素的索引作为dict的value
        # 此时dic[2]=0,dic[7]=1,dic[11]=2,dic[15]=3
        for i in range(len(nums)):
            dic[nums[i]] = i

        for i in range(len(nums)):
            # 防止将同一对符合条件的值重复加入，防止结果出现[0,1],[1,0]
            # i=0循环后，进入i=1时，1已经存在rList中所以会跳过，节省时间
            if i not in rList:
                # 将符合条件的两个元素成为互补元素
                # 差值是字典的key且对应互补元素的下标不是当前元素的下标
                # i=0时为例:9-2=7->dic[7]存在 and dic[7]=1!=0,所以i=0符合条件
                if (target - nums[i]) in dic.keys() and dic[target - nums[i]] != i:
                    # 当前元素没有参与过之前的互补配对
                    # valueList初始为null
                    if nums[i] not in valueList:
                        # rList = {0,1}
                        rList.append(i)
                        rList.append(dic[target - nums[i]])
                # valueList = {2}
                valueList.append(nums[i])

        return rList
-->