两数之和

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

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

示例：

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

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

解决该方法最容易的版本是，首先固定一个数 nums[i]，然后遍历数组查看是否包含 target-nums[i] 的数字，代码如下：

public int[] twoSum(int[] nums, int target) {
    int[] res = new int[2];
    // 首先固定 nums[i]
    for (int i = 0; i < nums.length - 1; i++) {
        // 接着在剩下的数字查找是否有数字等于 target - nums[j] 
        // 或者说 nums[i] + nums[j] = target
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                res[0] = i;
                res[1] = j;
                return res;
            }
        }
    }
    return res;
}

使用这种双重循环的方法，它的时间复杂度是 $O(n^2)$。

那有没有只需要扫描一遍数组即可以确定答案的办法，答案是有，我们可以利用哈希表做这件事情。我们在遍历数组时，我们将数组中的数字以及对应的下标以键值对的形式添加到一个哈希表中，每次我们在遍历一个数字 nums[i] 时，在添加该数字到哈希表之前(之所以是之前，以防一个数字被用两次，可以自己举个例子想想)，都在哈希表中查看是否有数字为 target - nums[i]，因为向哈希表查询的时间复杂度为 $O(1)$，所以这种只用遍历一遍数组即可知道解的方法，它的时间复杂度为 $O(n)$，代码如下：

public int[] twoSum(int[] nums, int target) {
    int[] res = new int[2];
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        // 首先进行查询，查询完了在将 nums[i] 添加到哈希表中
        if (map.containsKey(target - nums[i])) {
            res[0] = map.get(target - nums[i]);
            res[1] = i;
            break;
        }
        map.put(nums[i], i);
    }
    return res;
}

现在我们对上面的题目加个条件，给定的数组是有序的，且是从小到大排序的，那么有没有更快的方法来找到答案。

如果数组是有序的话，那么我们可以使用双指针的解法，首先一个指针指向数组的开头，即最小的那个数字，另一个指针指向数组的末尾，即最大的那个数字。接着我们通过移动这两个指针来找到答案

• 如果这两个指针指向的数字之和大于 target，那么我们要将指向末尾的指针向前移，因为第一个指针指向的数是最小的数，所以这时任何数加上后一个指针指向的数都会比 target 大，所以该数不可能是解，排除
• 如果小于，那么指向开头的指针向前移，道理同上，因为这时任何一个数和第一个指针指向的数相加都小于 target，所以该指针指向的数不可能是解，排除
• 如果等于，那就是找到了

以下图为例：

代码如下：

public int[] twoSum(int[] nums, int target) {
    int p1 = 0;
    int p2 = nums.length - 1;
    int[] res = new int[2];
    while (p1 < p2) {
        if (nums[p1] + nums[p2] == targets) {
            res[0] = p1;
            res[1] = p2;
            break;
        }
        if (nums[p1] + nums[p2] < target) {
            p1++;
        } else {
            p2--;
        }
    }
    return res;
}