LeetCode 167. 两数之和 II - 输入有序数组：JavaScript 双指针解法

题目链接：leetcode-cn.com/problems/tw…

解题思路

我们可以使用解常规两数之和问题所使用的暴力法或者哈希表法，该题目解法请见：

• 1. 两数之和：JavaScript 三种解法，暴力和哈希表

但那样并没有利用本题有序数组的条件。我们应该想一下，如何利用该条件来进一步降低算法复杂度。

因为是有序数组，我们使用两个指针，初始分别位于数组第一个元素和最后一个元素的位置，比较这两个元素之和与目标值的大小。如果和等于目标值，我们就找到了这个唯一解。如果和比目标值小，我们将较小的指针增加一。如果和比目标值大，我们将较大指针减小一。移动指针后重复上述比较，直至找到答案。

假设 是按升序排列的输入数组，并且元素 是唯一解。因为我们从左向右移动较小的指针，从右向左移动较大的指针，总有某个时刻存在一个指针移动到 或 的位置。不妨假设小指针先移动到了元素 ，这时两个元素的和一定比目标值大，根据我们的算法，我们会向左移动较大的指针直至获得结果。

代码

根据上述过程，实现代码如下：

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    let low = 0;
    let high = numbers.length - 1;

    while (low < high) {
        let sum = numbers[low] + numbers[high];
        if (sum == target) {
            return [low + 1, high + 1];
        } else if (sum > target) {
            high--;
        } else {
            low++;
        }
    }
    return ("No such two value!");
};

复杂度分析：

• 时间复杂度：
• 空间复杂度：

扩展

解本题时，我们对两个指针所指的元素进行了求和，那么我们是否需要考虑 溢出呢？按照本题出题的意思是不需要考虑，因为题目描述中说了，每个输入对应唯一解。因为数组是有序数组，所找的目标值 肯定也是一个整数，算法在寻找结果的时候，是通过移动指针位置逐步逼近目标值的，所以肯定会先寻找到目标值，而不会溢出。

但是，其实有特殊情况，例如输入数组为 ，目标值为 17。类似的特例可以举出很多种，这时则需要考虑溢出，而且这个考虑过程会异常复杂，因为特例的情况非常多，代码逻辑也会十分复杂，感兴趣的可以自己思考一下。不过这并不是本题的出题意图，本题主要是想让大家根据题目中有序数组的条件，通过双指针法对算法复杂度进行优化。

更多题解请关注：github.com/leviding/le…

关注公众号「技术漫谈」加算法群，每天一道算法题，趣学算法很容易！：

• LeetCode 算法题解
• JavaScript 入门到进阶
• 前端项目从零到一实战
• 前端学习方法路线分享
• ……