算法实战：滑动窗口解决水果成篮与字母异位词

初期方案可以使用 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 的维护。这种写法避免了频繁的容器操作，在实际运行中速度更快。

滑动窗口的精髓在于'动'。通过调整窗口边界，我们能在一次遍历中完成复杂的状态维护。掌握这一模式，很多看似棘手的子串问题都能迎刃而解。