宿州金融网站建设,163邮箱注册申请注册官网,广州免费自助建站开发,小杨哥直播带货平台题目#xff1a; 给定两个字符串 s 和 p#xff0c;找到 s 中所有 p 的 异位词 的子串#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串#xff08;包括相同的字符串#xff09;。
示例 1: 输入: s “cbaebabacd”, …题目 给定两个字符串 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-leftt.size()时在进行缩小滑动窗口操作进去后if判断vaild和need中的元素个数是否相等如果相等保存left的所有下标再缩小窗口if再need中有这个字母并且该字母的个数和window中的个数相等那么vaild–window也–。 class Test_zArr {
public:vectorint slidingWindow(string s,string t) {unordered_mapchar, int need,window;vectorint vee;for (char tt:t) {need[tt];}int left 0,right 0;int vaild 0;while (rights.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;vectorint result Tz.slidingWindow(s, t);for (vectorint::iterator it result.begin(); it ! result.end();it) {cout *it ;}cout endl;return 0;
}
