中国建设银行网站 党费云太原网站建设方案优化

题目： 给定两个字符串 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” 的异位词。

思路：

首先：使用滑动窗口模板，先确定向右移动移动过程中元素有need中的元素时，进行window的++，如果某个字母和need和window中相等时，进行vaild++，内存while可以更改为if，当right-left==t.size()时，在进行缩小滑动窗口操作，进去后if判断vaild和need中的元素个数是否相等，如果相等保存left的所有下标，再缩小窗口，if再need中有这个字母，并且该字母的个数和window中的个数相等，那么vaild–，window也–。

class Test_zArr {
public:vector<int> slidingWindow(string s,string t) {unordered_map<char, int> need,window;vector<int> vee;for (char tt:t) {need[tt]++;}int left = 0,right = 0;int vaild = 0;while (right<s.size()) {char c = s[right];right++;if (need.count(c)) {window[c]++;if (window[c] == need[c]) {vaild++;}}while (right - left == t.size()) {if (vaild == need.size()) {vee.push_back(left);}char d = s[left];left++;if (need.count(d)) {if (window[d] == need[d]) {vaild--;}window[d]--;}}}return vee;}
};int main() {Test_zArr Tz;string s = "cbaebabacd";string t = "abc";vector<int> result = Tz.slidingWindow(s, t);for (vector<int>::iterator it = result.begin(); it != result.end();it++) {cout << *it << " ";}cout << endl;return 0;
}