题目描述

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

例子：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 
输入：nums = [3,2,4], target = 6
输出：[1,2]
输入：nums = [3,3], target = 6
输出：[0,1]

哈希表法

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        #哈希表
        dic = {}
        N = len(nums)
        for i in range(N):
            if target - nums[i] in dic: 
                return [i,dic[target - nums[i]]] 
            dic[nums[i]] = i 

时间复杂度是O(N), 空间复杂度也是O(N),因为创建了dic ，这就是典型的用空间换取时间。

改编，把数组变成有序数组的话，那可以用二分法和双指针法来做。题目如下：

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target

例子：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 
输入：numbers = [2,3,4], target = 6
输出：[1,3]
输入：numbers = [-1,0], target = -1
输出：[1,2]

(1) 双指针

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        #双指针 
        N = len(numbers)
        p = 0 
        q = N -1 
        while p < q: 
            tmp = numbers[p] + numbers[q]
            if tmp == target: return [p+1, q+1]
            elif tmp > target: q -= 1 
            else: p += 1 

时间复杂度是O(N)

（2）二分法

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        #二分法 
        N = len(numbers)
        for i in range(N):
            bgn = i+1 
            end = N-1 
            while bgn <= end:
                mid = (bgn+end)//2
                tmp = numbers[mid]
                if tmp == target - numbers[i]: return [i+1,mid+1]
                elif tmp > target - numbers[i]: end = mid -1 
                else: bgn = mid + 1 
        return []

时间复杂度是O(nlogn)