目录
1.长度最小的子数组
2.无重读字符的最长字串
3. 最大连续1的个数
4.将x减小到0的最小操作数
5.水果成篮
6.找到字符串中所有字母异位词
7.串联所有单词的子集
8.最小覆盖字串
1.长度最小的子数组
. - 力扣（LeetCode）
对于从同一端往另一端移动的双指针，我们可以采用滑动窗口的策略解决。
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int ret = INT_MAX; int left = 0; int sum = 0; int right =0; for(left = 0, right = 0; right < nums.size(); right++) { sum += nums[right];//进窗口 while(sum >= target)//判断 { ret = min(ret,right - left + 1); sum -= nums[left]; left++; } } return ret == INT_MAX ? 0 : ret; return ret; } };如例子 2 3 1 2 4 3
我们让left和right从下标为0处出发，让right不断右移，一直让left到right这段的子数组之和大于等于目标数。
当left到right这段的子数组之和大于等于目标数时，再向后移动时，子数组的长度会更长，因此我们通过将left右移，判断能否减去一些较小的数，使范围内的子数组长度减小，但是仍然大于目标数。若可以，将每次的结果和ret比较
比如 1 2 3 4 50 ，目标数为40.
直到子数组小于目标数了，在让right右移。
但也有可能，整个数组加起来都达不到目标数的大小，我们可以事先遍历判断，也可以判断ret是否被赋值过，来进行返回
2.无重读字符的最长字串
. - 力扣（LeetCode）
class Solution { public: int lengthOfLongestSubstring(string s) { int hash[128] ={0}; int size = s.size(); int left = 0; int right = 0; int ret = 0; for(right; right < size; right++) { hash[s[right]]++; while(hash[s[right]] >1) { hash[s[left]]--; left++; } ret = max(ret,right-left + 1); } return ret; } };3. 最大连续1的个数
. - 力扣（LeetCode）
class Solution { public: int longestOnes(vector<int>& nums, int k) { int ret = 0; int sum = 0; int size =nums.size(); int left = 0; int right = 0; for(right; right < size; right++) { if(nums[right] == 0)sum++; while(sum > k) { if(nums[left] == 0)sum--; left++; } ret = max(ret,right - left + 1); } return ret; } };4.将x减小到0的最小操作数
. - 力扣（LeetCode）
class Solution { public: int minOperations(vector<int>& nums, int x) { int target = 0; int size = nums.size(); for(int i = 0 ;i < size; i++) { target += nums[i]; } target -= x; if(target < 0)return -1;//如果数组总和还没有x大，那就不能把x减到0，直接返回-1 int left = 0; int right = 0; int count = 0; int ret = -1; for(;right < size; right++) { count += nums[right]; while(count > target) { count -= nums[left]; left++; } if(count == target)(ret = max(ret,right-left + 1)); } return ret == -1 ? ret : size - ret; } };这个题目直接正面做不好做，我们可以转化为子数组中和为x的最长长度
这样即可用滑动窗口做题
5.水果成篮
. - 力扣（LeetCode）
class Solution { public: int totalFruit(vector<int>& fruits) { int n = fruits.size(); vector<int>arr(n,0); int left = 0; int right = 0; int count = 0; int ret = 0; for(;right < n;right++) { arr[fruits[right]]++; if( arr[fruits[right]] == 1)count++; while(count > 2) { arr[fruits[left]]--; if( arr[fruits[left]] == 0)count--; left++; } if(count >= 1)ret = max(ret,right-left+1); } return ret; } };这里我们引进一个计数器， 用于判断是否需要出窗口。
仅有新水果第一次入窗口，count才会增加。
当count > 2 时出窗口。
6.找到字符串中所有字母异位词
. - 力扣（LeetCode）
首先我们还是先存一个哈希表，用一个数组简单表示就可以了。
hash1表示目标字符串中的字符情况，hash2表示left到right字符串中的字符情况
#define N 128 class Solution { public: bool judge(int* hash1,int* hash2) { for(int i = 0; i < N; i++) { if(hash1[i] != hash2[i])return false; } return true; } vector<int> findAnagrams(string s, string p) { int size = p.size(); int hash1[N] = {0}; for(int i = 0; i < size; i++) { hash1[p[i]]++; } int hash2[N] = {0}; vector<int> ret; int left = 0; int right = 0; for(right;right < s.size(); right++) { hash2[s[right]]++; while(right- left +1 > size)//这里其其实用if更合适，因为窗口的长度固定，达到长度之 //后，right移动一次，left移动一次，最多只会超过一个 { hash2[s[left]]--; left++; } if(judge(hash1,hash2))ret.push_back(left); } return ret; } };第一个代码的思路和前面一样，先入窗口，判断长度不能超过目标字符串长度，进行出窗口，然后再判断是否符合条件。
我们这里写一个判断函数，来判断hashi1和hash2一样不一样。
class Solution { public: vector<int> findAnagrams(string s, string p) { int size = p.size(); int hash1[128] = {0}; for(int i = 0; i < size; i++) { hash1[p[i]]++; } int hash2[128] = {0}; int count = 0; vector<int> ret; int left = 0; int right = 0; for(right;right < s.size(); right++) { hash2[s[right]]++; if(hash2[s[right]]<= hash1[s[right]])count++; if(right-left+1 > size) { hash2[s[left]]--; if(hash2[s[left]] < hash1[s[left]])count--; left++; } if(count == size)ret.push_back(left); } return ret; } };第二个代码时间复杂度要低很多，这里我们维护一个count，来计算有效字符的个数。
我们进行入窗口操作时，我们先入窗口，然后判断，当hash2中对应位置 <= hash1中对应位置时，该字符有效，也就是我们还需要这个字符，比如我们需要两个a，当入窗口后a的个数为1，或者a的个数为2，我们都是需要的，此时count + 1。
当字符串里面的字符超过我们需要的值时，对该字符的计数增加，但是有效字符数不增加，这时候我们就可能遇到right-left+1 > 目标字符串长度 ，这时候我们不断出窗口，直到符合要求，这时候我们也同时判断有效字符是否减小。
7.串联所有单词的子集
. - 力扣（LeetCode）
class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { int len = words[0].size(); int size = words.size(); unordered_map<string,int> hash1;//储存words的hash1 for(auto ch:words) { hash1[ch]++; } vector<int> ret; for(int i = 0; i < len; i++) { int count = 0; int left =i; int right = i; unordered_map<string,int> hash2;//储存遍历的hash2 for(;right <s.size(); right+= len) { //入窗口，substr(right,right+len) string in = s.substr(right,len); hash2[in]++; if(hash1[in] && hash2[in] <= hash1[in])count++; while(right - left + 1 > len * size) { string out = s.substr(left,len); hash2[out]--; if(hash1[out] && hash2[out] < hash1[out])count--; left+= len; } if(count == size)ret.push_back(left); } } return ret; } };由于words中所有单词都是等长的，因此我们可以将一个字符串看为一组，以字符串的长度len为窗口一次滑动的距离，即单位长度 。
然后定义一个哈希表，思路同6
8.最小覆盖字串
. - 力扣（LeetCode）
class Solution { public: string minWindow(string s, string t) { int hash1[128]={0}; int hash2[128] ={0}; int kinds = 0; int count = 0; int minlen = INT_MAX; int begin = -1; for(auto ch:t) { hash1[ch]++; if(hash1[ch] == 1)kinds++; } for(int left = 0,right = 0,count = 0;right < s.size();right++) { int in = s[right]; hash2[in]++; if(hash2[in] == hash1[in])count++; while(count == kinds) { if(right - left + 1 < minlen) { minlen = right-left+1; begin = left; } int out = s[left]; hash2[out]--; if(hash2[out] < hash1[out])count--; left++; } } if(begin == -1)return ""; else return s.substr(begin,minlen); } };定义两个哈希表
我们这里采用kinds变量来储存遍历时需要进行判断的种类数。利用count计数判断
当hash1与hash2中同位置的值相等，count++。即有一个字符满足了题目要求。
这题要求我们取最小长度，所以我们right一直向右移动直到left到right包含所有的目标字符，然后出窗口，查看是否有更优解。
