滑动窗口算法实战：水果成篮与字母异位词
滑动窗口是处理连续子数组或子串问题的利器。今天我们通过两道经典题目——'水果成篮'和'找到字符串中所有字母异位词'，来拆解它的核心逻辑。
水果成篮
核心思路
这道题要求在一个数组中找到只包含两种元素的最长子数组。乍一看像阅读理解，其实本质就是寻找满足条件的最大窗口。暴力解法需要遍历所有起点，复杂度高达 O(N²)，显然不够高效。
我们可以用两个指针 left 和 right 维护一个窗口。关键在于统计窗口内不同元素的种类数。当种类超过 2 时，移动 left 指针缩小窗口，直到满足条件。这里使用定长数组模拟哈希表来记录每种水果的数量，因为数据范围已知且固定。
代码实现
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int hash[100001] = {0}; // 记录每种水果的数量
int ans = 0, kinds = 0; // kinds 记录当前窗口内的水果种类
for(int left = 0, right = 0; right < fruits.size(); right++) {
// 进窗口：更新计数，若新种类则增加种类数
if(hash[fruits[right]]++ == 0) kinds++;
// 出窗口：种类过多时收缩左边界
while(kinds > 2) {
if(--hash[fruits[left++]] == 0) kinds--;
}
// 更新最大长度
ans = max(ans, right - left + 1);
}
return ans;
}
};
这段代码的时间复杂度降到了 O(N)，运行效率显著提升。
找到字符串中所有字母异位词
核心思路
异位词是指由相同字符组成的排列。判断两个字符串是否互为异位词，不需要全排列比较，只需统计字符频次即可。
这是一个典型的固定长度滑动窗口问题。我们需要在字符串 s 中截取长度为 p.size() 的子串，检查其字符频次是否与 p 一致。
初期方案可以使用 unordered_map 存储频次，但考虑到字符集较小（仅小写字母），使用数组模拟哈希表能大幅减少内存分配开销，提升性能。同时，引入一个计数器 kinds 来跟踪有效字符匹配情况，避免每次比较整个数组。
代码实现
初始版本使用哈希表：
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ans;
unordered_map<char,int> hash1, hash2;
for(auto e : p) hash1[e]++;
for(int left = 0, right = 0; right < s.size(); right++) {
hash2[s[right]]++;
if((right - left + 1) > p.size()) {
char out = s[left];
if(--hash2[out] == 0) hash2.erase(out);
left++;
}
if(hash1 == hash2) ans.push_back(left);
}
return ans;
}
};
虽然逻辑正确，但哈希表的插入删除操作开销较大。优化后的数组版本如下：
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ans;
int hash1[26], hash2[26] = {0};
int kinds = 0;
for(auto e : p) hash1[e - 'a']++;
for(int left = 0, right = 0; right < s.size(); right++) {
// 进窗口：如果当前字符频次未超过目标，说明是有效字符
if(++hash2[s[right] - 'a'] <= hash1[s[right] - 'a']) kinds++;
// 出窗口：超出长度需移除左侧字符
if(right - left + 1 > p.size()) {
char out = s[left++];
if(hash2[out - 'a']-- <= hash1[out - 'a']) kinds--;
}
// 有效字符数等于目标长度，说明找到异位词
if(kinds == p.size()) ans.push_back(left);
}
return ans;
}
};
注意下标转换 -'a' 以及进出窗口时对 kinds 的维护。这种写法避免了频繁的容器操作，在实际运行中速度更快。
滑动窗口的精髓在于'动'。通过调整窗口边界，我们能在一次遍历中完成复杂的状态维护。掌握这一模式，很多看似棘手的子串问题都能迎刃而解。
