【优选算法】探索双指针之美（一）: 同向双指针缔造滑动窗口

前言：

在上一章中想必我们已经领略到了双指针和单调性相遇后擦出的美妙火花，在这章中我们就来一起探索一下同向双指针又有怎样的独特风味

1.长度最小的子数组

题目链接：LCR 008. 长度最小的子数组
题目叙述： 给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入： target = 7, nums = [2,3,1,2,4,3]
输出： 2
解释： 子数组[4,3]是该条件下的长度最小的子数组。

示例 2：

输入： target = 4, nums = [1,4,4]
输出： 1

示例 3：

输入： target = 11, nums = [1,1,1,1,1,1,1,1]
输出： 0

---

解题思路：
  解法一：暴力枚举
找出数组中全部的子数组，并求出每个子数组的和
时间复杂度：O(n^3)

---

在暴力枚举的基础上进行优化：
在加法中加的数越多和越大（前提这些数都是>0的）
模拟暴力枚举：
先定义一个左区间left,right，开始时都指向元素的起始位置；定义一个sum：以left，right为左区间的所有子数组之和
可以直接将时间复杂度优化为O(n^2)

---

  解法二：利用单调性，使用“同向双指针”（滑动窗口）来优化
1.初始化两个指针left,right用来充当窗口的左端和右端
2.进窗口
3.判断
4.出窗口
5.更新结果：更新结果要就题论题，有的题进窗口前更新，有的出窗口前判断后更新

用滑动窗口模拟实现：

时间复杂度：O(n)
利用单调性，规避了很多没有必要的枚举

代码实现：

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size(),sum = 0,len = INT_MAX;//因为是求len的min所以最开始时len定义成无穷大for(int left = 0,right = 0;right < n;right++){sum += nums[right];//进窗口while(sum >= target)//判断{len = min(len,right - left + 1);//更新结果sum -= nums[left++];//出窗口}}return len == INT_MAX ? 0 : len;}
};

2.无重复字符的最小字串

题目链接：LCR 016. 无重复字符的最长子串
题目描述： 给定一个字符串s，请你找出其中不含有重复字符的 最长连续子字符串 的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子字符串是 "abc"，所以其长度为 3。

示例 2:

输入:s= "bbbbb"
输出: 1
解释: 因为无重复字符的最长子字符串是 "b"，所以其长度为 1。

示例 3:

输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 "wke" ，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:

输入: s = “”
输出: 0

---

解题思路：

在解题之前，我们首先来了解一下哈希表
  1.是什么？
哈希表是一个存储数据的容器
  2.有啥用？
“快速”查找某个元素 ,快到 o(1)级别
 3.什么时候用哈希表？
频繁查找某一个数的时候
 4.怎么用哈希表？

1. 任何高级语言都有哈希表这个容器
2. 用数组模拟一个简易的哈希表

解法一： 暴力枚举+哈希表

固定每一个有可能的起始位置，依次向后扩展，直到扩展到不能扩展为止

用哈希表判断有无重复字符

时间复杂度：O(n^2)

暴力解法的优化：

定义一个left,right指针指向数组的起始位置，再加一个哈希表用来保存这段区间的字符信息。
模拟： 先判断right指向的字符在不在哈希表里面，不在将right指向的字符丢入哈希表中，right++
当right走到这个位置时
发现 right指向的字符在哈希表中，这时停止枚举操作，前面这段就是我最长的长度
所以以d为开头的最长长度就是到c这个位置。
按照暴力枚举策略，下来left将指向下一个位置，right也要回到left的位置，继续刚才的步骤。我们就会发现right又将会走到上图a这个位置，所以以第一个a为分界线的左区间为起始位置，right最多能走到第二个a的位置。因为a和a重复了。

所以：
1.right没有拐回来的必要，因为left已将跳过了重复的字符，所以目前的区间里面一定没有重复的字符。
2.当区间有重复字符时，先让left跳过重复字符，接下来再操作

解法二：利用规律，使用“滑动窗口”解决问题

1.先定义left = 0,right = 0来充当窗口的左右端点
2.进窗口 -> 让字符进入哈希表
3.判断 -> 窗口内出现重复字符

 出窗口 -> 从哈希表中删除该字符

更新结果

时间复杂度：O(n)

代码实现：

class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = { 0 }; //使用数组表示哈希表，让下标表示字符，让里面的数表示出现的个数。int left = 0,right = 0,n = s.size();int ret = 0;while(right < n){hash[s[right]]++;//进入窗口while(hash[s[right]] > 1)//判断hash[s[left++]]--;//出窗口ret = max(ret,right - left + 1);//更新结果right++;//让下一个元素进入窗口}return ret;}
};

3. 最大连续1的个数 III

题目链接：1004. 最大连续1的个数 III
题目描述：
给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多k个0 ，则返回 数组中连续 1 的最大个数 。

示例 1：

输入： nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出: 6
解释：[1,1,1,0,0,1,1,1,1,1,1]

粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

输入： nums= [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出： 10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]

粗体数字从 0 翻转到 1，最长的子数组长度为 10。

---

解题思路：
由于反转操作比较麻烦，可以将原始的问题转化为：找出数组中最长的子数组，这个子数组的条件是0的个数不超过k个。

 解法一：暴力枚举，将数组中所有的子数组全部枚举出来

优化暴力解法：
1.定义一个left指针来表示起始位置
2.定义一个right指针向后遍历每个元素，去找到最优的位置
3.定义一个zero来统计0出现的次数
模拟暴力操作：
开始往后移动
当right移动到这个位置时，zero恰好等于2，right可以继续往后移动一位

当right走到现在这个位置时，此时的zero等于3，红线部分表示固定首元素时的最优解

如果是暴力枚举策略，下一步left应该移动到下一个位置，right应当移到与left相同的位置处。

继续上述操作，我们就会发现right又走到了三角形标记的位置，此时的最优解为画红线的这一段。
为什么right又会跑到三角标记的地方呢？原因是区间内有连续的三个0,当left在以三角为界的左边区间固定时，right最大跑到三角标记的地方。所以right没有必要回到与left相同的位置处。

所以我们的策略是让right先别动，让left越过这段区域，使得zero重新变成2，此时不让right回来，让right向后移动。

所以
 解法二：利用滑动窗口解决问题

1. left = 0,right = 0;
2. 进窗口 ->right向后移动时就相当于每个元素进窗口，碰到1直接跳过，碰到0，zero+1;
3. 判断 ->zero > k

 出窗口 -> left是1直接跳过，是0 计数器-1

更新结果

代码实现：

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int ret = 0;for(int left = 0,right = 0,zero = 0;right < nums.size();right++){if(nums[right]==0) zero++; //进窗口while(zero > k) //判断if(nums[left++] == 0) zero--;//出窗口ret = max(ret,right - left + 1);//更新结果}return ret;}
};

时间复杂度：O(n)

4. 将 x 减到 0 的最小操作数

题目链接：1658. 将 x 减到 0 的最小操作数
题目描述： 给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组nums最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：

输入： nums = [1,1,4,2,3], x = 5
输出： 2
解释： 最佳解决方案是移除后两个元素，将x减到 0 。

示例 2：

输入： nums = [5,6,7,8,9], x = 4
输出： -1

示例 3：

输入： nums = [3,2,20,1,1,3], x = 10
输出： 5
解释： 最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

---

解题思路：
由于这道题从正面做起来会比较吃力，那么我们就采取 “正难则反” 的策略。

题目的大概意思是让我们在左端找一段区间a，在右端找一段区间b，使得两个区间加起来的和为x
那么我们就可以将问题转化为在中间找一段区间使得中间这段区间的和为sum - x;其中sum为这个整数数组的总和。

转化：找出最长的子数组的长度，使得所有元素的和正好等于 sum - x（target）

 解法一：暴力解法
先固定一个left，再固定一个right，让right依次向后移动找最佳的位置。

如何找最佳的位置呢？
定义一个tmp变量，记录一下left和right这段区间的和，当tmp>=target的时候right停下来
暴力枚举策略的下一步：left向后移动一位，right移动到left的位置，继续上述操作，我们会发现

**所以：**当left向后移动一位后,right没有必要回到left的位置去，right要么不动，要么向后移动即可。
&emsp；解法二：滑动窗口

1.left= 0;right=0;

2.进窗口 -> tmp+=nums[right]

3.判断 -> tmp > target （这里不能判断等于，因为等于是我们想要的结果）

 出窗口 -> tmp-=nums[left]

更新结果 -> tmp == target

代码实现：

class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum = 0;for(int a:nums) sum += a;int target = sum - x;//细节问题if(target < 0) return -1;int ret = -1;for(int left = 0,right = 0,tmp = 0;right<nums.size();right++){tmp += nums[right];//进窗口while(tmp>target)//判断tmp-=nums[left++];//出窗口if(tmp == target)//更新结果ret = max(ret,right - left + 1);}if(ret == -1) return ret;elsereturn nums.size() - ret;}
};

时间复杂度：O(n)

最后想说：

本章我们的滑动窗口问题就介绍到这里，下期我将进一步介绍关于滑动窗口的更多问题，如果这篇文章对你有帮助，记得点赞，评论+收藏 ，最后别忘了关注作者，作者将带领你探索更多关于编程方面的问题。