前端学数据结构与算法(十二):有趣的算法 – 多指针与滑动窗口

时间:2021-2-20 作者:admin

上一篇:前端学数据结构与算法(十一):看似简单又让人抓狂的二分查找算法

前言

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

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。