关于javascript:图解两数之和双指针法

两数之和是一道十分经典，也十分高频的面试题，题目粗心如下：

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

之前咱们探讨了这个问题的暴力运算法和哈希表法，明天咱们应用双指针法来解决它。

太长不看版

• 首先排序数组；
• 应用 left，right 两个指针；
• 比拟 target 与left值加 right 值的和，挪动对应的指针；
• 双指针解法的工夫复杂度取决于对应的排序算法，空间复杂度为 O(n)。

什么是双指针？

双指针和疾速排序、冒泡排序等具体算法不同。它更靠近于一种思（tào）路，一种应用两个指针互相配合来存储节点以便于运算的技巧。

双指针法实用于数组、链表等线性数据结构，罕用的思路有：碰撞指针、滑动窗口、快慢指针等。

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

0. 排序

所谓碰撞指针，是指在有序数组中定义left（数组起始地位）、right（数组终止地位）两个指针，在遍历时依据对应条件的不同来判断应该挪动哪个指针，进而从数组两端遍历数组。

所以在两数之和中咱们须要先将指标数组进行排序：

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

1. 创立双指针

在排好序的数组（以下简称数组）两端别离创立 left、right 指针：

2. 左移右指针

此时 left 值与 right 值之和（以下简称 sum）大于target，此时应该将right 左移一位，减小 sum 使其更靠近target。

从这里就能够看出，为什么对有序数组才实用碰撞指针。

3. 持续遍历数组

在这个 case 中咱们须要持续遍历数组，直到 right 指针指向 7，此时 sum 小于target：

4. 右移左指针

与步骤 2 相似，当 sum 小于 target 时咱们须要右移左指针，减少 sum 值使得两者更加靠近：

5. 匹配胜利！

在以后 case 中，left指向 2 时 sum 与target相等，匹配胜利！
此时返回 left 值和 right 值在原数组中的下标即可：

6. 残缺示例代码

示例代码如下：

须要留神的是，因为 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(n²)、空间复杂度 O(1)；
• 哈希表法工夫复杂度和空间复杂度都是 O(n)；
• 考察点是对哈希表这种数据结构的相熟水平；
• 多一种解法就多一分胜算；
• 整体难度不高。

一入 JS 深似海，心愿这个专栏能在你乘风破浪的旅途中有所帮忙。欢送关注我的公众号：「JS 散步指南」，更多精彩期待您发现！