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

分析

这道题是适合使用滑动窗口来解决。一开始，我们可以先比较字符串 s 和 p 的长度。当 s.length() < p.length() 时，直接返回空数组。接下来，我们可以定义两个长度为26的数组 s_count[] 和 p_count[]。并将 p.length() 个字符分别加入 s_count[] 和 p_count[] 中。若此时 s_count[] 和 p_count[] 相等，则意味着我们找到了第一个异位词，起始索引为 $0$ 。此时，我们将 $0$ 压入数组 ans 中。随后，我们开始滑动窗口。先弹出最左侧字符 --s_count[s[i] - 'a']，然后将 s[i + p.length()] 加入 s_count[] 中。此时我们比较 s_count[] 和 p_count[] 是否相等。若相等则说明我们找到了一个异位词，起始索引为 $i + 1$ ，将其压入数组 ans 中。随后，返回数组 ans 即可。

上面这个方法有个问题：每次都需要比较 s_count[] 和 p_count[] 是否完全相等，这浪费了不少时间。因此我们可以考虑使用一个变量 differ 以及一个数组 count[]。用 count[] 存储窗口内字符与 p 字符数的差。用 differ 记录 count[] 的非零元素个数，即当前窗口与字符串 p 中数量不同的字母的个数。然后我们统计一下情况

\begin{cases} \text{字符 c 离开窗口} & \mathrm{count[c]} - 1 = & \begin{cases} 0 & \text{一个多余字符被移除，differ} - 1 \\ -1 & \text{平衡被打破，有新的差异项。differ} + 1 \end{cases} \\ \text{字符 c 进入窗口} & \mathrm{count[c]} + 1 = & \begin{cases} 0 & \text{一个缺失的字符被添加，differ} - 1 \\ 1 & \text{平衡被打破，有新的差异项。differ} + 1 \end{cases} \end{cases}

也就是说，我们可以仅考虑 differ 的变化来判断当前窗口是否满足要求。

解答

1
class Solution {
2
public:
3
  vector<int> findAnagrams(string s, string p) {
4
    int s_len = s.length(), p_len = p.length();
5
    if (s_len < p_len)
6
      return vector<int>{};
7

8
    vector<int> count(26), ans;
9

10
    for (auto i = 0; i < p_len; ++i) {
11
      ++count[s[i] - 'a'];
12
      --count[p[i] - 'a'];
13
    }
14

15
    auto differ =
16
        count_if(count.begin(), count.end(), [](int c) { return c != 0; });
17

18
    if (differ == 0)
19
      ans.emplace_back(0);
20

21
    for (auto i = 0; i < s_len - p_len; ++i) {
22
      if (count[s[i] - 'a'] == 1)
23
        --differ;
24
      else if (count[s[i] - 'a'] == 0)
25
        ++differ;
26

27
      --count[s[i] - 'a'];
28

29
      if (count[s[i + p_len] - 'a'] == -1)
30
        --differ;
31
      else if (count[s[i + p_len] - 'a'] == 0)
32
        ++differ;
33

34
      ++count[s[i + p_len] - 'a'];
35

36
      if (differ == 0)
37
        ans.emplace_back(i + 1);
38
    }
39

40
    return ans;
41
  }
42
};