前言

如果说如何用算法高效有趣的解决某些问题，那多指针和滑动算法绝对是算其中的佼佼者。这也是笔者最初接触算法时觉得最有意思的一点，因为解决的问题是熟悉的，但配方却完全不同，本章我们从一个简单的交集问题出发，一步步的认识到多指针及滑动窗口解决某些问题时的巧妙与高效，本章主要以解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鼓捣一番，当时觉得代码量少还挺好。不过在深入理解了算法之后才明白，代码少不代表效率高，解题的逻辑思维能力才是最重要的。