滑动窗口算法：查找字符串中的字母异位词

1. 核心思路

滑动窗口是解决子串问题的常用技巧。对于寻找字母异位词，关键在于维护一个固定长度的窗口，并高效判断窗口内的字符组成是否与目标字符串一致。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;
        if (s.empty() || p.empty() || s.size() < p.size()) return result;
        
        int len = p.size();
        vector<int> hash(26, 0);
        for (char c : p) hash[c - 'a']++;
        
        int count = 0; // 统计有效字符数
        for (int i = 0; i < len; ++i) {
            if (hash[s[i] - 'a'] > 0) count++;
            hash[s[i] - 'a']--;
        }
        
        if (count == len) result.push_back(0);
        
        for (int i = len; i < s.size(); ++i) {
            // 出窗口
            if (hash[s[i - len] - 'a'] >= 0) count--;
            hash[s[i - len] - 'a']++;
            
            // 进窗口
            if (hash[s[i] - 'a'] > 0) count++;
            hash[s[i] - 'a']--;
            
            if (count == len) result.push_back(i - len + 1);
        }
        return result;
    }
};

2. 知识点导图

3. 题目描述

找到字符串中所有字母异位词

要点：

• 找子串
• 异位词：相同字母排列组合形成的字符串

怎么快速判断两个字符串是不是异位词？

创建两个哈希表

4. 解题

4.1 暴力解法

1. 以 p 的长度 n 为单位，暴力枚举 s 中的所有 n 元组。
2. 把 n 元组扔进哈希表中统计元素及其个数。
3. 与另一哈希表（统计 p）比对。
   • 时间复杂度 O(N^3)，必然超时。

4.2 优化解法

4.2.1 双指针优化

和之前的思路一样，通过同向双指针，把嵌套 for 的 O(N^2) 干成 O(N)。

最终复杂度为 O(N^2)：比对哈希表的过程中还有一次遍历还能优化。

4.2.2 计数变量优化

外层循环已经被优化了，我们现在来看内部遍历哈希表的过程能不能优化下，或者说我们换一种方式来维护窗口信息。

现在我来尝试用例子来模拟 hash 统计子串数据：

我们在用 hash 统计子串数据的过程中，我们发现：

我们统计的 s 中的数据可以分成两类：有效数据和无效数据

并且我们发现，当有效数据的个数和 hash1 中的数据个数相同，且 L=n 的时候。此时的子串完全符合要求。

因此，我们要做的事就从遍历对比两个哈希表数据变成了统计有效数据的个数。

因此，我们要创建一个 count 变量来统计有效数据的个数，并在窗口中不断维护它。

代码逻辑

1. 先用 hash1 统计 p 的元素。
2. 滑动窗口：
   • 进窗口：right 元素进 hash2
   • 判断：L>n
   • 出窗口：判断出的元素是否是有效元素，维护 count
   • 更新信息：L=n，count=p.size()；返回 left

5. 总结

通过引入计数变量 count，避免了每次移动窗口后重新遍历哈希表进行比对，将比较操作的时间复杂度从 O(K) 降为 O(1)，整体算法时间复杂度优化至 O(N)。