1.问题描述
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
示例 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" 的字母异位词。
2.说明
字母异位词指字母相同，但排列不同的字符串。
输入：
输入两个字符串s和p，只包含小写英文字母，长度都不超过 20100
输出：
输出一系列整数，为子串的起始索引，按照由小到大的顺序输出，整数之间以空格分隔。
如果起始索引集合为空，则输出“none”，不包括引号。
3.范例：
输入：
cbaebabacd
abc
输出：
0 6
4.思路
方法1：移动窗口子串
len定义为p字符串长度，遍历s字符串，每次取长度从 i 开始，长度为len的字符串给word，并对word和p字符串进行排序，已进行判断是否相同，相同则将 i 存入结果。
方法2：双指针
head指针，指向异位词子串头元素，初始值0；
tail指针，指向异位词子串未元素的下一个元素位置，初始值为0；
chars[128]数组，记录p字符串的每个字符数，初始值为0.
遍历s字符串，判断是否符合异位词子串了。具体逻辑如下所示：
【逻辑1】如果tail指针指向的字符，在chars中对应的值大于0，则执行减1操作，并且执行tail++；
【逻辑2】否则，获得head指针指向的字符，然后针对该字符在chars数组中的位置处执行加1操作，并且执行head++；
【逻辑3】当满足逻辑1的情况下，我们判断如果tail减去head等于p的长度，那么就说明我们找到了p的异位词子串，则将head复制给结果List即可。
思路参考：https://zhuanlan.zhihu.com/p/626490026
注意！！！输出要求，整数之间使用空格隔开，但输出最后一个索引时，不需要空格！！！
5.代码
方法1：移动窗口子串--缺点，运行速度慢
#include <iostream> #include <stdio.h> #include <string> #include <vector> #include <algorithm> using namespace std; class Solution { public: vector<int> findAnagrams(string s,string p) { vector<int> res; string word=""; int len=p.length(); for(int i=0;i<s.length();i++) { word=s.substr(i,len); sort(p.begin(),p.end()); sort(word.begin(),word.end()); if(p==word) { res.push_back(i); } } return res; } }; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); string s,p; cin>>s>>p; vector<int> res=Solution().findAnagrams(s,p); if(res.size()==0) cout<<"none"; else
for(int i=0;i<res.size();i++)
{
cout<<res[i];
if(i!=res.size()-1)
cout<<" ";
}
return 0; }
方法2：双指针，哈希表
#include <iostream> #include <stdio.h> #include <string> #include <vector> #include <algorithm> using namespace std; class Solution { public: //双指针，哈希表 vector<int> findAnagrams(string s,string p) { vector<int> res; int head=0;//指向异位词子串头元素 int tail=0;//指向异位词子串未元素的下一个元素位置 int chars[128]={0};//记录p字符串的每个字符数 for(int i=0;i<p.length();i++) { chars[p[i]]++; } while(tail<s.length()) { if(chars[s[tail]]>0) { chars[s[tail++]]--; if((tail-head)==p.length()) res.push_back(head); } else chars[s[head++]]++; } return res; } }; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); string s,p; cin>>s>>p; vector<int> res=Solution().findAnagrams(s,p); if(res.size()==0) cout<<"none"; else for(int i=0;i<res.size();i++) { cout<<res[i]; if(i!=res.size()-1) cout<<" ";//注意输出要求，在输出最后一个索引时，不需要使用空格分隔 } return 0; }