前端学数据结构与算法（十二）：有趣的算法 - 多指针与滑动窗口

前言

如果说如何用算法高效有趣的解决某些问题，那多指针和滑动算法绝对是算其中的佼佼者。这也是笔者最初接触算法时觉得最有意思的一点，因为解决的问题是熟悉的，但配方却完全不同，本章我们从一个简单的交集问题出发，一步步的认识到多指针及滑动窗口解决某些问题时的巧妙与高效，本章主要以解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 

初看这题可能很懵逼，或者就是使用两层循环的暴力解，求出每种可能，找里里面最大值，面试官对这个解法肯定不会满意。

而这道经典题目，我们同样可以使用对撞指针解法，首先设置首尾两个指针，依次向中间靠近，但这题麻烦的地方在于两个指针之间谁动谁不动的问题。

经过观察不难发现，就是指针所指向的值，谁的数值小，谁就需要移动。因为如果数值大的指针向中间移动，小的那个值的指针并不会变，而它们之间的距离会缩短，乘积也会变小。一次遍历即可解决战斗，解题代码如下：

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³)。如果这题是要返回它们对应的下标，那还真没办法，不过既然是返回组合的数字，那我们就可以利用有序数组的特性，还是使用对撞指针更有效率的解决此题。

首先对数组进行排序，然后设置三个指针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看成是一个窗口，在原有数组上进行滑动，每经过一个子数组就求出的它的平均值。如果使用暴力解，会存在重复计算的问题，所以我们每次滑动一步，只需要加上新的元素，然后减去窗口最左侧的元素即可。

解题代码如下：

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处，重新开始判断统计长度。图示如下：

代码如下：

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了，那么此时窗口的长度就是连续子数组的长度。

当找到一个连续子数组后，让左侧的窗口向右滑动，减去最左侧的值，减小窗口内的和，也让窗口右侧滑动。如果又找到了一个满足条件的子数组，与之前的子数组长度进行比较，更新最小窗口的大小即可。

有一个特例就是，如果整个数组加起来的和都比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里将其本身及窗口左侧的元素全部都移除，重复这个过程，直到窗口右侧到达字符串的末尾。如图所示：

解题代码如下：

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鼓捣一番，当时觉得代码量少还挺好。不过在深入理解了算法之后才明白，代码少不代表效率高，解题的逻辑思维能力才是最重要的。