创意网站设计团队,织梦做淘宝客网站,胶州网站建设公司,松江网站建设公司文章目录 1.题目示例提示 2.解答思路3.实现代码结果 4.总结 1.题目
给定两个字符串 s 和 p#xff0c;找到 s 中所有 p 的 异位词 的子串#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串#xff08;包括相同的字符串找到 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 * 104s 和 p 仅包含小写字母
2.解答思路
对于滑动窗口的题关键就是定义两个leftright用来控制子串的头尾。 还需要明确增大窗口的条件以及缩小窗口的条件。
定义一个vector对象用来存储答案答案就是每一次的left值。 定义两个无序哈希表分别存储s和p中字符出现的次数。 其中pCount的次数是不变的用来比较的标准。 其中sCount的次数是随着逐渐的遍历用来控制增大缩小窗口的关键判断条件。 当sCount中字符对应次数大于pCount中次数时就需要缩小窗口。
3.实现代码
class Solution
{
public:vectorint findAnagrams(string s, string p){vectorint answer ;unordered_mapchar, 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]]--; // 相对应字符次数减1left; // 缩小窗口}// 缩小窗口之后子串[left,right]两侧都是闭区间if (right - left 1 pLen){ // 当子串长度p长度就可记录下此时的left值answer.push_back(left);}}return answer;}
};结果 4.总结
这道题不简单写了好久。最开始没有考虑到p中有重复字符的情况导致饶了很大圈子。 最后还是参考别人的代码思路仿写的。学习了很好的思路。有收获
当两个序列的元素都需要计数的时候可以使用两个哈希表并且int型的值都会初始化为0.直接使用运算也是ok的。
自信坚持upup
