滑动窗口-----找到所有字母异位词

🔥个人主页：Milestone-里程碑

❄️个人专栏: <<力扣hot100>> <<C++>><<Linux>>

       <<Git>><<MySQL>>

🌟心向往之行必能至

题目理解

给定两个字符串 s 和 p，我们需要在 s 中找到所有是 p 的字母异位词的子串，并返回这些子串的起始索引。字母异位词指的是字母相同但排列不同的字符串，比如 abc 和 cba 就是一对异位词。

核心思路

这道题的核心是判断 s 中的子串是否与 p 包含完全相同的字符。滑动窗口是处理这类子串匹配问题的绝佳选择，我们可以维护一个动态的窗口，让它在 s 上滑动，并通过字符计数来快速判断当前窗口是否符合条件。

代码实现

cpp

class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> v;
int ch[26] = {0};

// 初始化：统计 p 中每个字符的出现次数
for(int i = 0; i < p.size(); ++i)
ch[p[i] – 'a']++;

int left = 0;
// 右指针遍历整个字符串 s
for(int right = 0; right < s.size(); ++right)
{
int c = s[right] – 'a';
ch[c]–; // 右字符进入窗口，计数减一

// 如果当前字符计数小于 0，说明它在 p 中没有或数量超了
// 我们需要移动左指针，把它“挤”出去
while(ch[c] < 0)
{
ch[s[left] – 'a']++;
left++;
}

// 当窗口大小正好等于 p 的长度时，说明找到一个异位词
if(right – left + 1 == p.size())
v.push_back(left);
}
return v;
}
};

代码解释

复杂度分析

• 时间复杂度：O(n + m)，其中 n 是 s 的长度，m 是 p 的长度。每个字符最多被左右指针各访问一次，所以整体是线性的。
• 空间复杂度：O(1)，因为我们只用了一个大小为 26 的数组来计数，空间是固定的。