当前位置：首页 > news >正文

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

news 2025/6/10 7:15:53

在这里插入图片描述

🧠 题目解析

题目描述：

给定两个字符串 s 和 p，找出 s 中所有 p 的字母异位词的起始索引。

返回的答案以数组形式表示。

字母异位词定义：
若两个字符串包含的字符种类和出现次数完全相同，顺序无所谓，则互为字母异位词。
例如："abc" 和 "bca" 是异位词；"aab" 和 "aba" 也是。

✅ 解法一：定长滑动窗口 + 计数数组比较

基本思路：

使用两个数组分别统计 p 和 s 某个长度为 p.length() 的子串的字母频次。
每次滑动窗口右移一位，更新窗口内的字符频次，并比较两个数组是否相等。
若频次完全相同，则说明当前窗口是 p 的一个异位词。

🔍 C++ 实现

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ans;if (s.length() < p.length()) return ans;array<int, 26> cnt_p{}; // 存 p 中每个字母的出现次数array<int, 26> cnt_s{}; // 存 s 当前窗口中每个字母的出现次数for (char c : p) {cnt_p[c - 'a']++;}for (int i = 0; i < s.length(); ++i) {cnt_s[s[i] - 'a']++; // 当前字符进入窗口if (i >= p.length()) {// 超出窗口长度，移除最左字符cnt_s[s[i - p.length()] - 'a']--;}if (cnt_s == cnt_p) {// 当前窗口字符频次与 p 相同，记录左边界ans.push_back(i - p.length() + 1);}}return ans;}
};

🧮 复杂度分析

时间复杂度： O(n)，n 为 s 的长度，数组比较常数级。
空间复杂度： O(1)，使用两个长度为 26 的数组。

✅ 解法二：滑动窗口 + 字符差值平衡法

核心思想：

维护一个字符差值数组 cnt[26]，初始记录 p 中每个字符出现次数。
当字符进入窗口时，对应计数减一；字符离开时加一。
如果窗口中字符完全匹配，cnt 中所有值为 0。

🔍 C++ 实现

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ans;if (s.length() < p.length()) return ans;int cnt[26] = {0}; // 差值数组// 初始化 p 的频次for (char c : p) {cnt[c - 'a']++;}int left = 0;for (int right = 0; right < s.length(); ++right) {int idx = s[right] - 'a';cnt[idx]--; // 当前字符进入窗口// 如果某个字母用得太多，收缩左边界while (cnt[idx] < 0) {cnt[s[left] - 'a']++;left++;}// 若窗口长度等于 p 的长度，则说明是异位词if (right - left + 1 == p.length()) {ans.push_back(left);}}return ans;}
};