前言
如果说如何用算法高效有趣的解决某些问题，那多指针和滑动算法绝对是算其中的佼佼者。这也是笔者最初接触算法时觉得最有意思的一点，因为解决的问题是熟悉的，但配方却完全不同，本章我们从一个简单的交集问题出发，一步步的认识到多指针及滑动窗口解决某些问题时的巧妙与高效，本章主要以解LeetCode里高频题为参考~
多指针
349 - 两个数组的交集 ↓
给定两个数组，编写一个函数来计算它们的交集。
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/intersection-of-two-arrays
暴力解：
将两个数组共有的元素放入一个数组进行去重即可，去重需要使用set，那直接存入set完事。代码如下：
解法1：
var intersection = function (nums1, nums2) {
const set = new Set()
nums1.forEach(num => {
if (nums2.includes(num)) {
set.add(num)
}
})
return [...set]
};
以下简单假设两个数组的长度都是n，该解法属于暴力解，需要两重的循环，includes需要在数组里查找，所以内部也是遍历，最终的复杂度是O(n²)，有没有更高效的解法？
二分查找：
当然有，因为是查找问题，我们可以对两个数组分别排序，然后运用上一章我们学习到的二分查找法进行查找，替换includes的查找，那么最终的解法我们能优化到O(nlogn)级别，代码如下：
解法2：
var intersection = function (nums1, nums2) {
nums1.sort((a, b) => a - b)
nums2.sort((a, b) => a - b)
const set = new Set()
nums1.forEach(num => {
if (binarySearch(nums2, num)) {
set.add(num)
}
})
return [...set]
};
function binarySearch(arr, target) { // 二分查找
let l = 0;
let r = arr.length
while (r > l) {
const mid = l + (r - l) / 2 | 0
if (arr[mid] === target) {
return true
} else if (arr[mid] > target) {
r = mid
} else {
l = mid + 1
}
}
return false
}
首先对数据进行预处理，最终的代码行数比方法1多了不少，不过总的复杂度是3个O(nlogn)，比O(n²)快不少，还有更高效的解法么？
双指针：
当然，还可以使用一种双指针的解法，首先还是对两个数组进行排序，然后使用两个指针分别指着两个数组的开头，谁的数值小谁向后滑动，遇到相同的元素就放入set内，直至两个数组中有一个到头为止。代码如下：
解法3：
var intersection = function (nums1, nums2) {
nums1.sort((a, b) => a - b)
nums2.sort((a, b) => a - b)
let i = 0;
let j = 0;
const set = new Set()
while (i < nums1.length && j < nums2.length) { //有一个到头结束循环
if (nums1[i] === nums2[j]) { // 找到了交集
set.add(nums1[i]) // 放入set内
i++
j++
} else if (nums1[i] > nums2[j]) { // 谁数值小，+1 移动
j++
} else {
i++
}
}
return [...set]
};
整个复杂度需要对两个数组快排，然后双指针要走完两个数组，最终的复杂度是O(nlogn) + O(nlogn) + 2n，虽然总的复杂度还是O(nlogn)，不过效率会优于二分查找。
167 - 两数之和 II - 输入有序数组 ↓
给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
很自然的能想到暴力解，两层循环遍历，最终的复杂度是O(n²)，但这不是我们想到的。
很显然暴力解并没有利用到题目描述里的升序排列这个特性，而最终的结果是需要查找的，所以我们很自然能想到使用二分查找法。这确实也是一种更快的解题思路，能将最终的复杂度降低到O(nlogn)级别，大家可以尝试解决。
这里提供一种更巧妙的解题思路，对撞指针。我们可以设置头尾两个指针，每一次将它们的和与目标进行比较，如果比目标值大，尾指针向中间移动，减少它们相加的和；反之它们的和如果比目标值小则把头指针向中间移动，增加它们相加的和。因为是有序的数组，所以不用担心移动的过程中错过了目标值。代码如下：
var twoSum = function (numbers, target) {
let l = 0 // 左指针
let r = numbers.length - 1 // 右指针
while (r > l) { // 不能 r >= l，因为不能使用同一个值两次
if (numbers[r] + numbers[l] === target) {
return [l + 1, r + 1]
} else if (numbers[r] + numbers[l] > target) {
r-- // 右指针向中间移动
} else {
l++ // 左指针向中间移动
}
}
return []
};
11 - 盛最多水的容器 ↓
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
示例：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。
在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water
image
初看这题可能很懵逼，或者就是使用两层循环的暴力解，求出每种可能，找里里面最大值，面试官对这个解法肯定不会满意。
而这道经典题目，我们同样可以使用对撞指针解法，首先设置首尾两个指针，依次向中间靠近，但这题麻烦的地方在于两个指针之间谁动谁不动的问题。
经过观察不难发现，就是指针所指向的值，谁的数值小，谁就需要移动。因为如果数值大的指针向中间移动，小的那个值的指针并不会变，而它们之间的距离会缩短，乘积也会变小。一次遍历即可解决战斗，解题代码如下：
var maxArea = function (height) {
let max = 0 // 保存最大的值
let l = 0;
let r = height.length - 1
while (r > l) { // 不能相遇
const h = Math.min(height[r], height[l])
max = Math.max(h * (r - l), max) // 容量等于距离差 * 矮的那边条轴
height[r] > height[l] ? l++ : r-- // 移动矮轴的指针
}
return max
};
15 - 三数之和 ↓
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素a，b，c，使得a+b+c=0？
请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
nums = [-1, 0, 1, 2, -1, -4]
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
很容易想到的就是暴力解，使用三层遍历，将三个数字累加和的可能性都计算一遍，提取需要的组合即可，暴力解的复杂度是O(n³)。如果这题是要返回它们对应的下标，那还真没办法，不过既然是返回组合的数字，那我们就可以利用有序数组的特性，还是使用对撞指针更有效率的解决此题。
image
首先对数组进行排序，然后设置三个指针i、l、r，每一轮的循环下标i是固定不动的，让l和j对撞，最后根据它们相加的和来移动l和r指针。如果和正好等于0，那就找到了一种组合结果；如果大于0，就r--让r指针向中间移动；如果小于0，就l++让l指针向中间移动，该解法的复杂度是O(n²)。解题代码如下：
var threeSum = function (nums) {
nums.sort((a, b) => a - b) // 排序
const res = []
for (let i = 0; i < nums.length; i++) {
let l = i + 1
let r = nums.length - 1
if (nums[i] > 0) { // 如果第一个元素就大于0，后面也不用比了
break;
}
if (i > 0 && nums[i] === nums[i - 1]) { // 跳过相同的数字
continue
}
while (r > l) {
const sum = nums[i] + nums[l] + nums[r];
if (sum === 0) { // 正好找到
res.push([nums[i], nums[l], nums[r]])
while (r > l && nums[l] === nums[l + 1]) { // 跳过相同的数字，一个元素只用一次
l++
}
while (r > l && nums[r] === nums[r - 1]) { // 跳过相同的数字，一个元素只用一次
r--
}
r-- // 缩小范围
l++ // 缩小范围
} else if (sum > 0) {
r-- // 右指针移动，减少下次计算的和
} else { // sum < 0
l++ // 左指针移动，增加下次计算的和
}
}
}
return res
};
滑动窗口
643 - 子数组最大平均数 I ↓
给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
输入: [1,12,-5,-6,50,3], k = 4
输出: 12.75
解释: 最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
以参数k的长度为一个子数组，所以可以把k看成是一个窗口，在原有数组上进行滑动，每经过一个子数组就求出的它的平均值。如果使用暴力解，会存在重复计算的问题，所以我们每次滑动一步，只需要加上新的元素，然后减去窗口最左侧的元素即可。
image
解题代码如下：
var findMaxAverage = function (nums, k) {
let max = 0
let sum = 0
for (let i = 0; i < k; i++) {
sum += nums[i] // 先求出第一个窗口
}
max = sum / k // 第一个窗口的平均值
let j = k
while (nums.length > j) {
sum += nums[j] - nums[j - k] // 加上新元素，减去最左侧元素
max = Math.max(sum / k, max) // 与之前窗口的平均值比较
j++ // 向右滑动
}
return max // 返回最大窗口平均值
};
674 - 最长连续递增序列 ↓
给定一个未经排序的整数数组，找到最长且连续递增的子序列，并返回该序列的长度。
输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。
输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence
这题还是使用滑动窗口解决，为窗口定义两个下标l、r，既然是递增的，那么我们就要两两相邻的进行比较，当遇到的元素大于窗口最右侧值时，将下标l移至r处，重新开始判断统计长度。图示如下：
image
代码如下：
var findLengthOfLCIS = function (nums) {
let l = 0;
let r = 0;
let max = 0;
while (nums.length > r) { // 只要窗口还在数组内活动
if (r > 0 && nums[r - 1] >= nums[r]) { // 如果遇到的元素大于窗口最右侧值
l = r // 重新统计长度
}
max = Math.max(max, r - l + 1) // 统计最长的长度
r++ // 向右滑动
}
return max
};
209 - 长度最小的子数组 ↓
给定一个含有n个正整数的数组和一个正整数s，找出该数组中满足其和≥s的长度最小的连续子数组，并返回其长度。
如果不存在符合条件的子数组，返回 0。
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
题目的要求是要找一个连续子数组的和大于或等于传入是s，所以我们还是可以使用滑动窗口，统计窗口内的和，如果已经大于或等于s了，那么此时窗口的长度就是连续子数组的长度。
当找到一个连续子数组后，让左侧的窗口向右滑动，减去最左侧的值，减小窗口内的和，也让窗口右侧滑动。如果又找到了一个满足条件的子数组，与之前的子数组长度进行比较，更新最小窗口的大小即可。
image
有一个特例就是，如果整个数组加起来的和都比s小，那就不能返回窗口的长度，而是直接返回0。
代码如下：
var minSubArrayLen = function (s, nums) {
let l = 0
let r = 0
let sum = 0 // 窗口里的和
let size = nums.length + 1
// 窗口的大小， 因为是要找到最小的窗口，所以设置一个比最大还 +1 的窗口
// 如果能找到一个符合条件的子数组才会更新窗口的大小
while (nums.length > l) { // 让左边界小于整个数组，为了遍历到每一个元素
if (s > sum) {
sum += nums[r++] // 窗口和小于s，移动右窗口
} else {
sum -= nums[l++] // 窗口大于s，移动左窗口
}
if (sum >= s) { // 找到符合的子数组
size = Math.min(size, r - l) // 更新最小窗口的值
}
}
return size === nums.length + 1 ? 0 : size
// 如果size等于初始值，表示没有符合要求的子数组，否则有找到
};
3 - 无重复字符的最长子串 ↓
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
这题和上一题类似，滑动窗口不仅仅可以作用于数组，字符串也同样适用。
这题麻烦一点的地方在于还要定义一个set用于查找，当新加入窗口的元素set里没有时，就加入其中，窗口右移；如果有这个元素，需要将窗口移动到set里出现的位置，也就是在set里将其本身及窗口左侧的元素全部都移除，重复这个过程，直到窗口右侧到达字符串的末尾。如图所示：
image
解题代码如下：
var lengthOfLongestSubstring = function (s) {
const set = new Set();
let l = 0;
let r = 0;
let max = 0;
while (l < s.length && r < s.length) {
if (!set.has(s[r])) { // 如果查找表里没有
set.add(s[r++]); // 添加右移窗口
} else {
set.delete(s[l++]);
// 从左侧开始删除，直到把新加入的且在查找表里有的元素删除为止
// 然后窗口才会继续开始右滑
}
max = Math.max(max, r - l); // 更新最大的值
}
return max;
};
最后
以上很多题目也有其他的解法或暴力解，不仅仅局限只有多指针和滑动窗口才能解决，不过在应对难题时，有另一种解题的思路供参考，不过这两种算法对边界的处理能力要求挺高，要特别注意定义指针时开/闭区间的含义。
想起笔者之前在遇到算法题目之前要么暴力求解，或者就是使用各种遍历api鼓捣一番，当时觉得代码量少还挺好。不过在深入理解了算法之后才明白，代码少不代表效率高，解题的逻辑思维能力才是最重要的。
网友评论