两数之和是一道非常经典, 也非常高频的面试题, 题目大意如下:
给定一个整数数组 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(n2), 空间复杂度 O(1);
哈希表法时间复杂度和空间复杂度都是 O(n);
考察点是对哈希表这种数据结构的熟悉程度;
多一种解法就多一分胜算;
整体难度不高.
来源: https://segmentfault.com/a/1190000023552474