1. 首页
  2. IT资讯

图解两数之和:双指针法

image

两数之和是一道非常经典,也非常高频的面试题,题目大意如下:

给定一个整数数组nums 和一个目标值target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。
case:
给定 nums = [2, 1, 7, 11, 15], target = 9
因为 nums[0] + nums[2] = 2 + 7 = 9
所以返回 [0, 2]

之前我们探讨了这个问题的暴力运算法和哈希表法,今天我们使用双指针法来解决它。

太长不看版

  • 首先排序数组;
  • 使用leftright两个指针;
  • 比较targetleft值加right值的和,移动对应的指针;
  • 双指针解法的时间复杂度取决于对应的排序算法,空间复杂度为O(n)。

什么是双指针?

双指针和快速排序、冒泡排序等具体算法不同。它更接近于一种思(tào)路,一种使用两个指针互相配合来存储节点以便于运算的技巧。

双指针法适用于数组、链表等线性数据结构,常用的思路有:碰撞指针、滑动窗口、快慢指针等。

在两数之和这个case中我们使用碰撞指针的方式来实现,其它两种套路会在后续文章中介绍。

0.排序

所谓碰撞指针,是指在有序数组中定义left(数组起始位置)、right(数组终止位置)两个指针,在遍历时根据对应条件的不同来判断应该移动哪个指针,进而从数组两端遍历数组。

所以在两数之和中我们需要先将目标数组进行排序:


image


排序算法的时间复杂度决定了整个计算的时间复杂度。因为双指针遍历的复杂度是O(n)。

1.创建双指针

在排好序的数组(以下简称数组)两端分别创建leftright指针:


image


2.左移右指针

此时left值与right值之和(以下简称sum)大于target,此时应该将right左移一位,减小sum使其更接近target

从这里就可以看出,为什么对有序数组才适用碰撞指针。


image


3.继续遍历数组

在这个case中我们需要继续遍历数组,直到right指针指向7,此时sum小于target


image


4.右移左指针

与步骤2类似,当sum小于target时我们需要右移左指针,增加sum值使得两者更加接近:


image


5.匹配成功!

在当前case中,left指向2时sumtarget相等,匹配成功!
此时返回left值和right值在原数组中的下标即可:


image


6.完整示例代码

示例代码如下:


image


需要注意的是,由于JavaScript引用类型的特性,我们首先拷贝了nums,才使用Array.sort对拷贝数组进行排序。

另外,对于nums=[1,2,2,3],target=4这种case,其期望的返回值是[1,2]而不是[1,1]或者[2,2]。所以这里我们使用了Array.lastIndexOf()这个API。

小结

  • 采用碰撞双指针进行运算;
  • 碰撞双指针运算的时间复杂度取决于具体的排序算法,空间复杂度为O(n);
  • 碰撞指针需要对数组进行排序;
  • 排序时注意不要污染原数组;
  • 返回结果需要考虑数组含有相同项;

再复习一下暴力运算法和哈希表法:

  • 双层for循环暴力运算简单直观,时间复杂度O(n2)、空间复杂度O(1);
  • 哈希表法时间复杂度和空间复杂度都是O(n);
  • 考察点是对哈希表这种数据结构的熟悉程度;
  • 多一种解法就多一分胜算;
  • 整体难度不高。

本文来自投稿,不代表程序员编程网立场,如若转载,请注明出处:http://www.cxybcw.com/200328.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code