LeetCode 438. 找到字符串中所有字母异位词 —— 滑动窗口与 vector 常用操作

题目

LeetCode 438. Find All Anagrams in a String

给定两个字符串 s 和 p，找到 s 中所有 p 的字母异位词的子串，返回这些子串的起始索引。

• 字母异位词：由相同字母重新排列形成的字符串，字符种类与数量相同，顺序无关。

• 例：s = "cbaebabacd", p = "abc" → 输出 [0, 6]。

算法：定长滑动窗口 + 字符计数

核心思想：异位词只要求字符频次相同，与顺序无关。因此维护一个长度固定为 p.size() 的窗口，比较窗口内字符频次与 p 的字符频次即可。

步骤：

复杂度：时间 O(n)，空间 O(1)（26 个字母的定长数组）。

代码

class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> res;
int n = s.size(), m = p.size();
if (n < m) return res;

vector<int> need(26, 0), window(26, 0);
for (int i = 0; i < m; i++) {
need[p[i] – 'a']++;
}

for (int i = 0; i < n; i++) {
window[s[i] – 'a']++; // 右端入窗
if (i >= m) window[s[i – m] – 'a']–; // 窗口超过 m，左端出窗
if (i >= m – 1 && window == need) { // 窗口大小恰为 m 时比较
res.push_back(i – m + 1); // 记录起始下标
}
}
return res;
}
};

知识点：vector 常用操作

1. 初始化

vector<int> a; // 空
vector<int> a(26, 0); // 26 个元素，全 0
vector<int> a{1, 2, 3}; // 初始化列表：3 个元素
vector<vector<int>> mat(26, vector<int>(26, 0)); // 26×26 二维

注意 a(26) 是 26 个元素，a{26} 是 1 个元素值为 26，圆括号与花括号语义不同。

2. 存储与访问

a.push_back(x); // 尾部追加元素（动态扩容）
a[i]; // 下标访问，不检查越界
a.at(i); // 下标访问，越界抛 out_of_range
a.back(); // 最后一个元素
a.front(); // 第一个元素

3. 容量与大小

a.size(); // 元素个数
a.empty(); // 是否为空
a.reserve(1000); // 预分配容量，避免多次扩容
a.capacity(); // 当前容量

4. 修改

a.pop_back(); // 删除尾部元素
a.clear(); // 清空（size 变 0，capacity 通常不变）
a.insert(a.begin(), x); // 在指定位置插入
a.erase(a.begin()); // 删除指定位置元素
a.resize(10); // 调整大小

5. 遍历

for (int i = 0; i < a.size(); i++) cout << a[i];

for (const int& x : a) cout << x; // 范围 for，推荐

for (auto it = a.begin(); it != a.end(); ++it) cout << *it;

6. 比较

window == need; // 逐元素比较，相等返回 true

本例正是利用 vector 的 operator== 直接比较两个 26 长度的计数数组。

易错点小结