滑动窗口算法详解：从基础概念到实战应用
滑动窗口算法详解：从基础概念到实战应用
滑动窗口算法是一种高效的算法技巧，主要用于解决数组或字符串中子数组（子串）相关的问题。它本质上是双指针算法的衍生，通过控制两个指针的移动来动态维护一个区间，从而避免了暴力解法中重复计算的问题。本文将从基本概念出发，通过多个具体案例，深入讲解滑动窗口算法的原理和应用。
滑动窗口算法基础
滑动窗口算法的本质是使用双指针暴力解法，通过控制指针的移动来得到一个区间，这个区间就像一个“窗口”。当这个双指针在移动过程中表现出单调性（即始终从左往右移动）时，这个区间就被称为滑动窗口。
记住：
- 滑动窗口是暴力双指针解法的衍生，当left、right指针都是一直往右移时，就表示为滑动窗口。
- 在解题时，如果遇到需要处理连续子数组（子串）的问题，通常可以尝试使用滑动窗口算法。
滑动窗口算法的基本模板
滑动窗口算法的基本模板如下：
1. 初始化两个指针：left = 0，right = 0
2. 进窗口：维护窗口内的信息
3. 判断：根据窗口信息判断是否需要出窗口
- 如果需要出窗口：
- 出窗口
- 更新结果（位置不固定，需要根据题目要求放置）
滑动窗口算法的具体应用
1. 长度最小的子数组
题目描述：
给定一个数组和一个目标值，找到数组中和大于等于目标值的最短子数组。
分析：
暴力解法的时间复杂度为O(N^3)，通过使用前缀和优化可以降低到O(N^2)。进一步分析发现，由于窗口的单调性，可以使用滑动窗口算法，将时间复杂度优化到O(N)。
代码实现：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int sum = 0, res = INT_MAX;
for (int left = 0, right = 0; right < nums.size(); right++) {
sum += nums[right];
while (sum >= target) {
res = min(res, right - left + 1);
sum -= nums[left];
left++;
}
}
return res == INT_MAX ? 0 : res;
}
};
2. 无重复字符的最长子串
题目描述：
给定一个字符串，找到其中不包含重复字符的最长子串的长度。
分析：
通过使用哈希表记录字符出现的次数，可以在O(1)时间内判断窗口内是否有重复字符。当发现重复字符时，移动left指针直到重复字符被移出窗口。
代码实现：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (s.size() == 0) return 0;
int hash[128] = {0};
int res = INT_MIN;
for (int left = 0, right = 0; right < s.size(); right++) {
hash[s[right]]++;
while (hash[s[right]] > 1) {
hash[s[left]]--;
left++;
}
res = max(res, right - left + 1);
}
return res;
}
};
3. 最大连续1的个数 III
题目描述：
给定一个二进制数组和一个整数k，可以将最多k个0翻转成1，求最长的连续1的个数。
分析：
使用滑动窗口算法，当窗口内0的个数超过k时，移动left指针直到窗口内0的个数小于等于k。
代码实现：
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int zero = 0, res = 0;
for (int left = 0, right = 0; right < nums.size(); right++) {
if (nums[right] == 0) zero++;
while (zero > k) {
if (nums[left] == 0) zero--;
left++;
}
res = max(res, right - left + 1);
}
return res;
}
};
4. 将 x 减到 0 的最小操作数
题目描述：
给定一个数组和一个整数x，每次可以选择数组的开头或结尾的元素减去，求将x减到0的最小操作数。
分析：
通过转换思路，将问题转化为在数组中找到和为sum(nums) - x的最大子数组，然后用数组总长度减去这个最大子数组的长度。
代码实现：
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int target = accumulate(nums.begin(), nums.end(), 0) - x;
int n = nums.size();
if (target < 0) return -1;
int sum = 0, len = -1;
for (int left = 0, right = 0; right < n; right++) {
sum += nums[right];
while (sum > target) {
sum -= nums[left];
if (left < n) left++;
}
if (sum == target) len = max(len, right - left + 1);
}
return len == -1 ? -1 : n - len;
}
};
5. 水果成篮
题目描述：
给定一个数组，数组中的每个元素代表一种水果，每次可以选择连续的子数组，但子数组中只能包含两种不同的水果，求最长的子数组长度。
分析：
使用滑动窗口算法，当窗口内水果种类超过2种时，移动left指针直到窗口内水果种类小于等于2种。
代码实现：
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int kinds = 0, hash[100010] = {0}, res = 0;
for (int left = 0, right = 0; right < fruits.size(); right++) {
if (hash[fruits[right]] == 0) kinds++;
hash[fruits[right]]++;
while (kinds > 2) {
hash[fruits[left]]--;
if (hash[fruits[left]] == 0) kinds--;
left++;
}
res = max(res, right - left + 1);
}
return res;
}
};
6. 找到字符串中所有字母异位词
题目描述：
给定两个字符串s和p，找到s中所有与p是字母异位词的子串的起始索引。
分析：
使用滑动窗口算法，通过比较窗口内字符的个数与目标字符串的字符个数是否相等来判断是否为异位词。
代码实现：
class Solution {
public:
bool Check(int hash1[26], int hash2[26]) {
for (int i = 0; i < 26; i++) {
if (hash1[i] != hash2[i]) return false;
}
return true;
}
vector<int> findAnagrams(string s, string p) {
int hash1[26] = {0}, hash2[26] = {0};
for (auto c : p) hash2[c - 'a']++;
vector<int> res;
for (int left = 0, right = 0; right < s.size(); right++) {
hash1[s[right] - 'a']++;
if (right - left + 1 > p.size()) {
hash1[s[left] - 'a']--;
left++;
}
if (Check(hash1, hash2)) res.push_back(left);
}
return res;
}
};
7. 串联所有单词的子串
题目描述：
给定一个字符串s和一个字符串数组words，求s中所有包含words中所有单词的子串的起始索引。
分析：
将问题转化为在s中找到所有与words中单词排列相同的子串，使用滑动窗口算法，每次移动窗口的长度为words中单词的长度。
代码实现：
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> res;
unordered_map<string, int> hash2;
int n_hash2 = 0;
for (auto& s : words) {
n_hash2++;
hash2[s]++;
}
int len = words[0].size();
for (int i = 0; i < len; i++) {
unordered_map<string, int> hash1;
int count = 0;
for (int left = i, right = i; right < s.size(); right += len) {
string sub1 = s.substr(right, len);
hash1[sub1]++;
if (hash2.count(sub1) && hash1[sub1] <= hash2[sub1]) count++;
if (((right - left) / len) + 1 > n_hash2) {
string sub2 = s.substr(left, len);
if (hash2.count(sub2) && hash1[sub2] <= hash2[sub2]) count--;
hash1[sub2]--;
left += len;
}
if (count == n_hash2) res.push_back(left);
}
}
return res;
}
};
8. 最小覆盖子串
题目描述：
给定两个字符串s和t，求s中包含t所有字符的最小子串。
分析：
使用滑动窗口算法，当窗口内包含t中所有字符时，尝试缩小窗口以找到最短的子串。
代码实现：
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> hash1, hash2;
for (auto c : t) hash2[c]++;
int count = 0, len = INT_MAX, l_res = -1;
for (int left = 0, right = 0; right < s.size(); right++) {
hash1[s[right]]++;
if (hash2.count(s[right]) && hash1[s[right]] == hash2[s[right]]) count++;
while (count == hash2.size()) {
if (right - left + 1 < len) {
len = right - left + 1;
l_res = left;
}
if (hash2.count(s[left]) && hash1[s[left]] == hash2[s[left]]) count--;
hash1[s[left]]--;
left++;
}
}
return l_res == -1 ? "" : s.substr(l_res, len);
}
};
通过以上案例，我们可以看到滑动窗口算法在处理子数组（子串）相关问题时的强大威力。它通过动态维护一个窗口，避免了暴力解法中重复计算的问题，大大提高了算法的效率。希望本文能帮助读者深入理解滑动窗口算法，并在实际问题中灵活运用这一技巧。