findAnagrams

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

分析

初始化目标频率表：
- 使用哈希表 hash 存储字符串 p 中每个字符的频率
滑动窗口遍历字符串 s：
- 窗口初始范围为 [j, i]，窗口长度不超过 p.size()
- 遍历字符串 s，对窗口内的字符更新哈希表：
  - 窗口右扩（加入字符）：
    - 将当前字符 s[i] 加入窗口，并在 hash 中减少其频率
    - 如果该字符的频率变为 0，说明该字符的频率匹配，增加匹配计数 count
  - 窗口左缩（移除字符）：
    - 如果窗口长度超过 p.size()，将左端字符 s[j] 从窗口移除：
      - 如果 s[j] 在 hash 中频率变为非零，匹配计数 count 减少
      - 更新左指针 j
判断异位词：
- 如果窗口内所有字符频率均匹配（count == total），将当前窗口左端索引 j 加入结果集 res

时间复杂度

初始化哈希表：O(p)，其中 p 是字符串 p 的长度
滑动窗口遍历：O(s)，其中 s 是字符串 s 的长度

总时间复杂度：O(s + p)

空间复杂度

使用了一个哈希表存储字符频率，空间复杂度为 O(k)，其中 k 是字符集大小

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


class Solution
{
public:
    vector<int> findAnagrams(string s, string p)
    {
        std::unordered_map<char, int> hash; // 存储目标字符频率
        for (char c : p)
            ++hash[c];

        std::vector<int> res;
        int total = hash.size(), count = 0;

        for (int i = 0, j = 0; i < s.size(); ++ i)
        {
            // 右扩：加入字符 s[i]
            -- hash[s[i]];
            if (hash[s[i]] == 0)
                ++ count;

            // 左缩：移除字符 s[j]
            if (i - j + 1 > p.size())
            {
                if (hash[s[j]] == 0)
                    -- count;
                ++ hash[s[j]];
                ++ j;
            }

            // 检查是否找到异位词
            if (count == total)
                res.push_back(j);
        }

        return res;
    }
};