阅读 281

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

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

解题思路

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

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

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

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

代码

根据上述过程,实现代码如下:

/**
 * @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!");
};
复制代码

复杂度分析:

  • 时间复杂度:{O}(n)
  • 空间复杂度:{O}(1)

扩展

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

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

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


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

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

微信公众号

关注下面的标签,发现更多相似文章
评论