标签：数组、哈希表

题目在：two-sum

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路一：

采用一个字典，key是list里的值，value是值对应的在list中的index。依次在list循环，如果期望值和list中某值的差在数组中，就返回对应的两个index。如果不存在，就放入字典中，继续循环。
时间复杂度O（n），空间复杂度O（n）

还可以使用enumerate

def twoSum(self, nums, target):
    _dict = {}
    for i in range(len(nums)):
        expected = target - nums[i]
        if expected in _dict.keys():
            return [i, _dict[expected]]
        else:
            _dict[nums[i]] = i

def twoSum5(self, nums, target):
    hashset = {}
    for i in range(len(nums)):
        if hashset.get(target - nums[i]) is not None:
            return [i, hashset.get(target - nums[i])]
        hashset[nums[i]] = i

def twoSum6(self, nums, target):
    dic = {}
    for k, v in enumerate(nums):
        if target - v in dic:
            return [k, dic[target - v]]
        dic[v] = k

解题思路二：暴力

双层循环，强行得到结果
暴力算法时间复杂度O（n²），空间复杂度O（1）
def twoSum2(self, nums, target):
for i in range(len(nums)):
for j in range(1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []

解题思路三：

排序+双指针法
这里先将数组排序好O（nlogn），再利用双指针法遍历一遍O（n）得到结果。
为了保存下标信息另开了一个数组
时间复杂度O（nlogn），空间复杂度O（n）

    def twoSum3(self, nums, target):
        temp = nums.copy()
        temp.sort()
        i = 0
        j = len(nums) - 1
        while i < j:
            if (temp[i] + temp[j]) > target:
                j = j - 1
            elif (temp[i] + temp[j]) < target:
                i = i + 1
            else:
                break
        p = nums.index(temp[i])
        nums.pop(p)
        k = nums.index(temp[j])
        if k >= p:
            k = k + 1
        return [p, k]