LeetCode_Python(1)_两数之和

需求

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例：
给定 nums = [4, 11, 4, 15, 4]，target = 8
因为 nums[0] + nums[2] = 4 + 4 = 8 ，所以返回 [0, 2]

解决方案

方法一

---

1. 不重复利用同样的元素，即不能自己加自己，同一个元素也不能使用超过1次；
2. 每次输出只对应一个答案，即只有一对数据符合要求。
3. 使用Python内置函数enumerate()获取数组元素(value)及对应的索引(key)；
4. 如果target - value 在列表中，且其索引必须大于key，同时key不在target_list中，则将key和值target - value在列表nums中的索引位置，添加到target_list中即可。
5. 参考代码

def two_sum(nums, target):
    target_list = []
    for key, value in enumerate(nums):
        if (target - value) in nums[key+1:] and key not in target_list:
            target_list.extend([key, key + 1 + nums[key+1:].index(target - value)])
    return target_list

nums = [4, 11, 4, 15, 4]
target = 8
result = two_sum(nums, target)
print(result)
[0, 2]

方法二

---

1. 方法二仅对数列遍历一次，通过索引位数加一排除使用重复元素；
2. 对数列遍历后，将索引和值添加到字典中，同时对字典进行遍历，判断target-num是否在字典中，如果在则可以同时2个元素的索引位置。
3. 参考代码

def two_sum(num, target):
    d = {}
    for index, dig in enumerate(nums):
        item = target - dig
        for key, value in d.items():
            if value == item:
                return (key, index)
        d[index] = dig

nums = [4, 11, 4, 15, 4]
target = 8
result = two_sum(nums, target)
print(result)
(0, 2)

需求延伸

如果不要求每种输入只会对应一个答案，则结果可能有多对数据，对方法(一)中的target_list，通过列表推导式的方法，成对地输出，参考代码：

def get_target_index(nums, target):
    target_list = []
    for key, value in enumerate(nums):
        if (target - value) in nums[key+1:] and key not in target_list:
            target_list.extend([key, key + 1 + nums[key+1:].index(target - value)])

    result = [target_list[x:x+2] for x in range(0, len(target_list), 2)]
    return result

nums = [2, 6, 4, 11, 4, 15, 4]
target = 8
result = get_target_index(nums, target)
print(result)
[[0, 1], [2, 4]]