题目描述

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

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

样例

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

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

算法1

双指针

排序后利用双指针，排序要记录下标！

python 代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        l = 0
        k = 0
        r = len(nums)-1
        ans = []
        h = []

        for i in nums:
            h.append((i,k))
            k += 1
        h.sort()

        while l<r:
            if h[l][0] + h[r][0] > target:
                r -= 1
            elif h[l][0] + h[r][0] < target:
                l += 1
            else:
                ans.append(h[l][1])
                ans.append(h[r][1])
                break;
        return ans

算法2

字典

遍历列表，如果当前值为x，那么如果target-x已经存在于列表中，那么直接返回答案，否则，将x插入到字典中

python 代码

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        ans = []
        h = {}
        k = len(nums)

        for i in range(0,k):
            if target-nums[i] in h:
                ans += [i,h[target-nums[i]]]
                break;
            else:
                h[nums[i]] = i
        return ans;