算法：双指针 滑动窗口类型问题

滑动窗口问题 基本上就是 判断某个字符串P是否在其他字符串S里面出现过.

指针法+hash，具体思路是 用hash存取p节点的value-index值（这样方便查找O(1)），然后就是特别注意左指针是在啥时候移动的，这题由于滑动窗口大小固定了，因此判断条件为 right-left>=p.size()。 题目leetcode 76.最小覆盖子串这题由于没有固定滑动窗口大小，因此只能是判断是否valid==need.size()，如果符合，将左指针右移。

438. 找到字符串中所有字母异位词 给定一个字符串 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” 的字母异位词。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 代码：

class Solution { public: vector<int> findAnagrams(string s, string p) { unordered_map<char,int> need,window; for(char c:p) { need[c]++; } //双指针 int left=0,right=0; int valid=0; vector<int> ret_v; while(right<s.size()) { char c=s[right]; right++; if(need.count(c)) { window[c]++; if(window[c]==need[c]) { valid++; } } //左指针开始向右移动 while(right-left>=p.size()) { if(valid==need.size()) { ret_v.push_back(left); } char d=s[left]; left++; if(need.count(d)) { if(window[d]==need[d]) { valid--; } window[d]--; } } } return ret_v; } };

76. 最小覆盖子串 给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入：S = “ADOBECODEBANC”, T = “ABC” 输出：“BANC”

提示：

如果 S 中不存这样的子串，则返回空字符串 “”。 如果 S 中存在这样的子串，我们保证它是唯一的答案。

思路： 注意左指针移动条件，因为窗口没有固定，指针移动条件为valid==need.size() ==》 满足移动

class Solution { public: string minWindow(string s, string t) { unordered_map<char,int> need,window; for(char c:t) { need[c]++; } int left=0,right=0; int valid=0;//一般来说 valid=t.size() 就能够到达条件了 //下面这两个变量是根据中求最短的路径，我们需要求的 int start=0; int len=INT_MAX; while(right<s.size()) { char c=s[right]; //cout<<"c="<<c<<endl; right++;//这两句连在一起写，也就是现使用然后再加一 if(need.count(c)) { window[c]++; if(window[c]==need[c])//这就是代表滑动窗口中有有某个元素1已经符合条件了 { valid++; } } //窗口指针左移 while(valid==need.size())//条件。这点很重要，不同的题目可能只有这里改一下就基本可以了 { cout<<"进来了"; if(right-left<len) { start=left; len=right-left; } char d=s[left]; left++; if(need.count(d))//左结点出现了在need中的值 { if(window[d]==need[d]) { valid--; } window[d]--; } } } return len==INT_MAX ? "":s.substr(start,len); } };

567. 字符串的排列 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: s1 = “ab” s2 = “eidbaooo” 输出: True 解释: s2 包含 s1 的排列之一 (“ba”).

示例2:

输入: s1= “ab” s2 = “eidboaoo” 输出: False

思路 注意左指针移动条件，因为窗口固定，指针移动条件为right-left==s1.size() ==》 满足移动

代码：

class Solution { public: bool checkInclusion(string s1, string s2) { //滑动窗口 unordered_map<char,int> need,window; for(char c: s1) { need[c]++; } int left=0, right=0; int valid=0; while(right<s2.size()) { char c=s2[right]; right++;//先使用，将指针向后移动 if(need.count(c)) { window[c]++; if(window[c]==need[c]) { valid++; } } //移动滑动窗口 while(right-left>=s1.size())//我们需要将左指针右移 我们需要注意 right已经指向下一个元素了 { if(valid==need.size()) { return true; } char d=s2[left]; left++; if(need.count(d)) { if(window[d]==need[d]) { valid--; } window[d]--; } } } return false; } };