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;
    }
};

Python 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution:
  def findAnagrams(self, s: str, p: str) -> List[int]:
    freq = {}

    for ch in p:
      freq[ch] = freq.get(ch, 0) + 1

    total, count = len(freq), 0
    res = []

    j = 0
    for i in range(len(s)):
      freq[s[i]] = freq.get(s[i], 0) - 1
      if freq[s[i]] == 0:
        count += 1
      if i - j + 1 > len(p):
        if freq[s[j]] == 0:
          count -= 1
        freq[s[j]] = freq.get(s[j], 0) + 1
        j += 1
      if total == count:
        res.append(j)

    return res

Go 代码

 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


func findAnagrams(s string, p string) []int {
  freq := make(map[byte]int)
  for i := 0; i < len(p); i ++ {
    freq[p[i]] ++
  }

  total, count := len(freq), 0
  res := []int{}

  for i, j := 0, 0; i < len(s); i ++ {
    freq[s[i]] --
    if freq[s[i]] == 0 {
      count ++
    }
    if i - j + 1 > len(p) {
      if freq[s[j]] == 0 {
        count --
      }
      freq[s[j]] ++
      j ++
    }
    if count == total {
      res = append(res, j)
    }
  }
  return res
}

JavaScript 代码

 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


/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
  let freq = new Map();
  for (let i = 0; i < p.length; i++) {
    freq.set(p[i], (freq.get(p[i]) || 0) + 1);
  }

  let total = freq.size,
    count = 0;
  let res = [];

  for (let i = 0, j = 0; i < s.length; i++) {
    freq.set(s[i], (freq.get(s[i]) || 0) - 1);

    if (freq.get(s[i]) == 0) {
      count++;
    }

    if (i - j + 1 > p.length) {
      if (freq.get(s[j]) == 0) {
        count--;
      }
      freq.set(s[j], (freq.get(s[j]) || 0) + 1);
      j++;
    }

    if (total == count) {
      res.push(j);
    }
  }
  return res;
};