文章目录
- 1.题目
- 示例
- 提示
- 2.解答思路
- 3.实现代码
- 结果
- 4.总结
1.题目
给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。
示例
示例 1:
输入: s = “cbaebabacd”, p = “abc”
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例 2:
输入: s = “abab”, p = “ab”
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。
提示
- 1 <= s.length, p.length <= 3 * 104
- s 和 p 仅包含小写字母
2.解答思路
对于滑动窗口的题,关键就是定义两个left,right用来控制子串的头尾。
还需要明确增大窗口的条件,以及缩小窗口的条件。
定义一个vector对象,用来存储答案(答案就是每一次的left值)。
定义两个无序哈希表分别存储s和p中字符出现的次数。
其中pCount的次数是不变的,用来比较的标准。
其中sCount的次数是随着逐渐的遍历用来控制增大缩小窗口的关键判断条件。
当sCount中字符对应次数大于pCount中次数时,就需要缩小窗口。
3.实现代码
class Solution
{
public:
vector<int> findAnagrams(string s, string p)
{
vector<int> answer ;
unordered_map<char, int> pCount, sCount; // 无序哈希表
int pLen = p.size();
int sLen = s.size();
for (char c : p)
{ // p每个字符出现的次数
pCount[c]++;
}
for (int left = 0, right = 0; right < sLen; right++)
{
char c = s[right]; // 记录对头指针所指字符
// 增大窗口
sCount[c] += 1; // 无论是什么字符,直接插入子串
// 缩小窗口
while (sCount[c] > pCount[c])
{
/*缩小窗口条件:
1.当下字符不在p中。
2.当下字符出现重复(p中没有重复字符)
3.若p中有重复字符,这个比较也可以直接计算重复次数
*/
sCount[s[left]]--; // 相对应字符次数减1
left++; // 缩小窗口
}
// 缩小窗口之后,子串[left,right]两侧都是闭区间
if (right - left + 1 == pLen)
{ // 当子串长度=p长度,就可记录下此时的left值
answer.push_back(left);
}
}
return answer;
}
};
结果
4.总结
这道题不简单,写了好久。最开始没有考虑到p中有重复字符的情况,导致饶了很大圈子。
最后还是参考别人的代码思路仿写的。学习了很好的思路。有收获!
当两个序列的元素都需要计数的时候,可以使用两个哈希表,并且int型的值,都会初始化为0.,直接使用++运算也是ok的。
自信,坚持,upup~