前言
前面我们学习了什么是双指针，今天我将为大家分享一种特殊的双指针——滑动窗口，为什么说它是特殊的双指针呢？因为它也是有两个指针维护的，并且两个指针的移动方向是相同的，就跟我们平时生活中的窗口一样，两条边是往相同的方向移动的。
什么是滑动窗口
滑动窗口算法是一种用于解决数组或字符串相关问题的算法。它通过两个指针维护的一个窗口，在窗口内进行操作，并根据问题的要求移动窗口的起始位置或结束位置。
滑动窗口算法通常用于解决需要在连续子数组或子字符串中寻找最大值、最小值、满足特定条件的值等问题。它的基本思想是通过调整窗口的大小和位置，以便在不重复计算的情况下，高效地处理问题。
滑动窗口算法的步骤如下：
初始化窗口的起始位置和结束位置。
根据问题的要求，移动窗口的起始位置或结束位置。
在每次移动窗口时，根据窗口内的元素进行相应的操作，例如计算最大值、最小值、满足特定条件的值等。
重复步骤2和步骤3，直到窗口移动到数组或字符串的末尾。
滑动窗口算法的时间复杂度通常为O(n)，其中n为数组或字符串的长度。它通过避免重复计算，提高了问题的解决效率。
我们通过几个例子来了解滑动窗口算法。
1.长度最小的子数组
https://leetcode.cn/problems/minimum-size-subarray-sum/
1.1 题目要求
给定一个含有 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
提示：
1 <= target <= 109 1 <= nums.length <= 105 1 <= nums[i] <= 105
class Solution { public int minSubArrayLen(int target, int[] nums) { } }
1.2 做题思路
我们先来看看，如果使用暴力解法该怎么做。分别以每个数字开始，向后找 和>=target的子数组。
暴力解法是通过两层循环，i 从 0开始，j 从 i+1 开始遍历整个数字，找到 和 >= target 的长度最小的子数组。并且这个和是每次循环都从 0 开始加的。
通过观察每次循环找到的长度最小的子数组，我们可以发现，left 指针和 right 指针都是向同一个方向向右移动的，暴力解法是每次循环结束之后 right 的位置就回到 left + 1 的位置，这样就多了很多重复的不必要的计算。所以滑动窗口就是在这个暴力解法的基础上进行优化的，每次 right 的指向不进行返回，而是继续向右滑动，那么为什么 right 的指向可以不用返回呢？因为每次循环 left 的指向都会向右移动一位，而你要想找的长度最小的子数组的和 >= target，你的 right 就必须也是向右移动或者不移动，但是绝对不会是向左移动（在数组元素都是正数的情况下），这种就是滑动窗口的基本特征。
那么知道了使用滑动窗口这个算法的时候，我们来看看具体应该如何实现。定义一个 sum 变量，存储每次进窗口之后这个窗口元素的和，并且这个sum 不是每一次都是逐个累加而是用之前的 sum 加上进窗口的这个元素，当 sum >= target 的时候，就需要进行出窗口的操作，并且在出窗口的时候，还需要判断是否需要更新 ret 的值，继续寻找后面的长度最小的子数组，每出一个元素，sum 就需要减去这个出去的数，出窗口一直出到 sum < target，然后再进窗口，反复上面的操作，直到 right 到达数组末尾。
1.3 Java代码实现
class Solution { public int minSubArrayLen(int target, int[] nums) { int ret = Integer.MAX_VALUE; for(int left = 0,right = 0, sum = 0; right < nums.length; right++) { sum += nums[right]; while(sum >= target) { ret = Math.min(ret,right - left + 1); sum -= nums[left++]; } } return ret == Integer.MAX_VALUE ? 0 : ret; } }
2.无重复字符的最长子串
https://leetcode.cn/problems/longest-substring-without-repeating-characters/
2.1 题目要求
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
0 <= s.length <= 5 * 104 s 由英文字母、数字、符号和空格组成
class Solution { public int lengthOfLongestSubstring(String s) { } }
2.2 做题思路
先来看看暴力解法如何解决
通过暴力解法，我们也可以发现，每次循环找到的无重复字符的最长子串它的 left 的 right 都是向右移动的，所以这个题目同样使用滑动窗口来解决。
因为这里求的是长度最长的无重复字符的子串，所以需要在进窗口的时候进行判断是否需要更新最大长度，而判断是否有重复的字符，我们可以借助哈希表来进行判断。
2.3 Java代码实现
class Solution { public int lengthOfLongestSubstring(String ss) { char[] s = ss.toCharArray(); int[] hash = new int[128]; int ret = 0; for(int left = 0, right = 0; right < s.length; right++) { char in = s[right]; hash[in]++; if(hash[in] == 1) { ret = Math.max(ret,right - left + 1); } while(hash[in] > 1) { char out = s[left++]; hash[out]--; } } return ret; } }
3.最大连续1的个数 III
https://leetcode.cn/problems/max-consecutive-ones-iii/
3.1 题目要求
给定一个二进制数组 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。
提示：
1 <= nums.length <= 105 nums[i] 不是 0 就是 1 0 <= k <= nums.length
class Solution { public int longestOnes(int[] nums, int k) { } }
3.2 做题思路
很多人看到这个翻转0不知道啥意思，说通俗点就是0可以变成1，同样，先来看看暴力解法如何解决。
left 指针和 right 指针都是向右方向移动的，所以这道题目同样使用滑动窗口来解决。我们的判断条件是以窗口内0的数量为判断条件，并且求的是最大长度，所以是在进窗口的时候进行判断。
3.3 Java代码实现
class Solution { public int longestOnes(int[] nums, int k) { int ret = 0; for(int left = 0, right = 0,count = 0; right < nums.length; right++) { if(nums[right] == 0) count++; if(count <= k) { ret = Math.max(ret,right - left + 1); } while(count > k) { if(nums[left++] == 0) count--; } } return ret; } }
4.将x减到0的最小操作数
https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/
4.1 题目要求
给你一个整数数组 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 。
提示：
1 <= nums.length <= 105 1 <= nums[i] <= 104 1 <= x <= 109
class Solution { public int minOperations(int[] nums, int x) { } }
4.2 做题思路
这道题目的意思就是：给定一个数字x，每次从数组的最左边或者最右边选择一个数减去，然后使x减到0的最少的操作数。这道题目如果从正面去做的话，会先的非常麻烦，不妨我们换一条思路，他求的是数组两边减去的最少的数字，不妨我们就求数组中间最长的子数组，使它们的和为数组所有元素的总和减去 target ，这样就能是数组的两侧的和为 target 并且长度最短。所以这个题目就跟前面的求数组长度最长的子数组是差不多的，就只是判断的地方不同，这里需要在出窗口之后判断是否需要更新ret的值，这里我就不给大家过多介绍了，关键就是能够知道这个思路。
4.3 Java代码实现
class Solution { public int minOperations(int[] nums, int x) { int sum = 0; for(int n : nums) sum += n; //求数组所有元素的总和 int target = sum - x; if(target < 0) return -1; int ret = -1; for(int left = 0, right = 0,sum1 = 0; right < nums.length; right++) { sum1 += nums[right]; while(sum1 > target) { sum1 -= nums[left++]; } if(sum1 == target) { ret = Math.max(ret,right - left + 1); } } return ret == -1 ? -1 : nums.length - ret; } }
5.水果成篮
https://leetcode.cn/problems/fruit-into-baskets/
5.1 题目要求
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当* 符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。示例 1：
输入：fruits = [1,2,1] 输出：3 解释：可以采摘全部 3 棵树。
示例 2：
输入：fruits = [0,1,2,2] 输出：3 解释：可以采摘 [1,2,2] 这三棵树。 如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
示例 3：
输入：fruits = [1,2,3,2,2] 输出：4 解释：可以采摘 [2,3,2,2] 这四棵树。 如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
示例 4：
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4] 输出：5 解释：可以采摘 [1,2,1,1,2] 这五棵树。
提示：
1 <= fruits.length <= 105 0 <= fruits[i] < fruits.length
class Solution { public int totalFruit(int[] fruits) { } }
5.2 做题思路
根据题目我们可以知道，只有两个篮子，只能装两种水果，并且每个篮子可以装的水果数是无限的，这道题跟子数组的问题是类似的，只是判断条件变成了水果的种类，进窗口的时候，添加水果的种类很简单，当这个种类的水果数量在之前为0时，就说明是一个新的种类，但是当我们出窗口的时候，如果某一种类的水果数量减为0的时候，就需要减去一种种类，那么我们如何统计某一水果的数量呢？哈希表，使用哈希表可以很高效的对某一种类的数量进行统计。
5.3 Java代码实现
class Solution { public int totalFruit(int[] fruits) { int ret = 1; int[] hash = new int[fruits.length]; for(int left = 0, right = 0,kinds = 0; right < fruits.length; right++) { int in = fruits[right]; if(hash[in]++ == 0) kinds++; if(kinds <= 2) { //当水果的种类小于等于2的时候就需要做出判断 ret = Math.max(ret,right - left + 1); } while(kinds > 2) { int out = fruits[left++]; if(--hash[out] == 0) kinds--; } } return ret; } }
【算法系列篇】滑动窗口-2：https://developer.aliyun.com/article/1430505
