滑动窗口算法详解
(一) 长度最小的子数组
题目链接： https://leetcode.cn/problems/minimum-size-subarray-sum/
1.1 题目分析
这道题要求我们在数组中找一个区间，这个区间的元素的和等于题目给出的 target，如果找不到则返回 0。
1.2 算法原理
解法一：暴力遍历出所有的区间，然后找到最小区间。如果我们按照这种方法就需要两个循环才能解决问题，时间复杂度为 O(n^2)，效率非常低。
解法二：利用单调性，使用同向双指针（同向双指针就是我们的滑动窗口）。
1.3 代码实现
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int left = 0, right = 0, sum = 0, len = INT_MAX;
int n = nums.size();
while (right < n) {
sum += nums[right]; // 入窗口
while (sum >= target) { // 判断
len = min(len, right - left + 1); // 更新 len
sum -= nums[left++]; // 划出窗口
}
right++; // 再入窗口
}
return len == INT_MAX ? 0 : len;
}
};
(二) 无重复字符的最长子串
题目链接： https://leetcode.cn/problems/longest-substring-without-repeating-characters/
2.1 题目分析
题目的意思就是让我们找一个区间，在这个区间里的元素没有重复，返回区间的大小。
2.2 算法原理
解法一：暴力枚举 + 哈希表（去重）。
解法二：根据规律，使用滑动窗口来解决问题。
像上面两个常见的例子，我们的算法逻辑是将 right 所在的元素入哈希表，如果出现重复，我们就让 left++，当重复消失，这时更新一下 len 即可。
2.3 代码实现
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int left = 0, right = 0, len = 0;
int a[128] = {0}; // 用来观察是否有重复
while (right < s.size()) {
a[s[right]]++; // 入窗口
while (a[s[right]] > 1) {
a[s[left++]]--;
}
len = max(len, right - left + 1);
right++;
}
return len;
}
};
(三) 最大连续 1 的个数 III
题目链接： https://leetcode.cn/problems/max-consecutive-ones-iii/
3.1 题目分析
这个题的意思就是让我们找两个 0 的位置去翻转为 1，使全部为 1 的区间长度最长。
3.2 算法原理
这道题需要我们转换一下思路，如果我们老老实实的按照题目中的那样先将一个 0 翻转为 1，再找一个 0 翻转为 1，那就太复杂了。那我们转换一下思路，我们是不是可以找一个区间，这个区间里 0 的个数为题目中的 k，然后求这个区间最大的长度即可。
需要注意的是我们再入右区间的时候，这种情况下，left 需要++，只要 left 位置还等于 1，那区间一定在缩小，所以要是 left 当前的值不为 0 就直接跳过即可。
3.3 代码实现
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int left = 0, right = 0, count0 = 0, len = 0;
int n = nums.size();
while (right < n) {
if (nums[right] == 0) count0++; // 入窗口
while (count0 > k) { // 判断
if (nums[left] == 1) left++; // 跳过
else {
left++;
count0--; // 结束
}
}
len = max(len, right - left + 1); // 更新 len
right++;
}
return len;
}
};
(四) 将 x 减到 0 的最小操作数
题目链接： https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/
4.1 题目分析
这道题就是让我们在左右区间来删除元素，使题目中的 x 最后为 0。
4.2 算法原理
这道题也需要我们转换一下思路，如果我们来按照题目中的方法来左右一个一个删除的话，情况太多了，所以我们可以来找反面，正所谓'正难则反'嘛，所以我们就去找中间的区间，让中间的区间元素和为数组总元素和与 x 之差相等，再用一次滑动窗口求解出这个区间即可。
4.3 代码实现
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
}
int target = sum - x;
if (target < 0) return -1;
int left = 0, right = 0, len = -1, count = 0;
while (right < nums.size()) {
count += nums[right];
while (count > target) {
count -= nums[left++];
}
if (count == target) len = max(len, right - left + 1);
right++;
}
if (len == -1) return len;
else return nums.size() - len;
}
};
