滑动窗口算法详解
滑动窗口本质上也是双指针，但与前文介绍的相向移动不同，滑动窗口的两个指针是同向移动的。本文通过两个经典题目介绍滑动窗口的基本使用。
长度最小的子数组
题目描述
给定一个包含 n 个正整数的数组 nums 和一个正整数 target，找出该数组中满足其和 >= target 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
算法原理
滑动窗口的本质是两个指针同向移动，通过这两个指针的移动判断区间之和是否满足条件。如果满足就进行比较长度大小。
初始化时两个指针起点相同：
int left = 0, right = 0;
滑动窗口涉及两个操作：进窗口和出窗口。
- 进窗口：当区间之和 < target 时，需要更多数字参与，右指针向右移动。
- 出窗口：当区间之和 >= target 时，尝试缩小窗口以寻找更短长度，左指针向右移动。
代码实现
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int ans = INT_MAX, left = 0, right = 0, sum = 0;
for (; right < nums.size(); right++) {
sum += nums[right];
while (sum >= target) {
ans = min(ans, right - left + 1);
sum -= nums[left++];
}
}
return ans == INT_MAX ? 0 : ans;
}
};
无重复字符的最长子串
题目描述
给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。
算法原理
本题同样适用滑动窗口三部曲：第一是进窗口，第二是判断，第三是出窗口。 使用哈希映射（数组模拟）来判断是否存在重复字符。如果映射值大于 1，则说明有重复，需要出窗口直到满足条件。
代码实现
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int hash[256] = {0}, ans = 0;
for (int left = 0, right = 0; right < s.size(); right++) {
hash[s[right]]++;
while (hash[s[right]] > 1) {
hash[s[left++]]--;
}
ans = max(ans, right - left + 1);
}
return ans;
}
};