【Leetcode】001—Two Sum

一、题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例：

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

二、代码实现

方法一：暴力法

对于每个元素x，遍历数组其余部分来在查找是否存在一个与 target - x 相等的目标元素。

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for index in range(len(nums)):
            num = nums[index]
            if target - num in nums[index+1:]:
                return [index, index + 1 + nums[index+1:].index(target - num)]

时间复杂度：O(n^2）
空间复杂度：O(1)

方法二：字典法

维护一个dict，其key是nums中的数值，value是其index。先创建一个空字典，然后遍历数组，当前数是num，如果target-num已经在dict中，则返回[target-num, num]，否则将num加入dict中。

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        numdict = {}
        for index in range(len(nums)):
            num = nums[index]
            if target - num in numdict:
                return [numdict[target - num], index]
            numdict[num] = index

时间复杂度：O(n)（dict的查询复杂度为O(1)）
空间复杂度：O(n)
方法三：Two-pointers
对nums进行排序，然后两个指针分别从头尾进行扫描，若和为target，则返回index，否则，若小于target，左指针加1，若大于target，右指针减1。

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        nums = enumerate(nums)
        nums = sorted(nums, key=lambda x:x[1])
        l, r = 0, len(nums) - 1
        while l <= r:
            if nums[l][1] + nums[r][1] == target:
                return [nums[l][0], nums[r][0]]
            elif nums[l][1] + nums[r][1] < target:
                l = l + 1
            else:
                r = r - 1 

时间复杂度：O(nlogn）(sorted函数)
空间复杂度：O(n)