1.题目

原题

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

例子

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

2.解析

这道题三个思路：
思路1：暴力求解，O（n2），一般面试官不会让你用这种方法做。
思路2：双指针，解决几数之和的最有效思路，三四数之和，都可以用双指针来做，其实说白了数组的题都可以用双指针，目的就是化两次遍历为一次，化三次遍历为两次，以此类推吧。
这个题有点特殊，不是一个排序数组，首先给排一下序。
思路3：哈希表，就构建字典就能解。

3.python代码

##双指针法
class Solution:
    def twoSum(self, nums, target):
        import numpy as np
        numsindex = np.argsort(nums)
        nums.sort()
        start, end = 0, len(nums)-1
        while start < end:
            tmpsum = nums[start] + nums[end]
            if tmpsum == target:
                return [int(numsindex[start]), int(numsindex[end])]
            elif tmpsum > target:
                end -= 1
            elif tmpsum < target:
                start += 1
        return []