1.长度最小的子数组
209. 长度最小的子数组 - 力扣（LeetCode）
运用滑动窗口（同向双指针）来解决，因为这些数字全是正整数，在left位置确定的下，right++这个总sum会越大，所以我们先让nums[right]进窗口，然后判断sum是否大于等于target，如果大于等于就更新总长度len，再让left往右走。当right不满足条件时，就是找到最小的len。（这个算法的优点：利用单调性规避了很多不必要的遍历，时间复杂度O(2 * N)）。
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();int sum = 0, len = n + 1;for(int left = 0, right = 0; right < n; right++){sum += nums[right];while(sum >= target){len = min(len, right - left + 1);sum -= nums[left++];}}return len == n + 1 ? 0 : len; }
};2.无重复字符的最长子串
3. 无重复字符的最长子串 - 力扣（LeetCode）
解决思路：滑动窗口，定义一个hash数组来映射对应的值
进窗口：将右指针对应的字符放入hash数组中。
判断：当右指针对应的字符已经超过一个了，就开始移动左指针，让左指针出窗口。
更新结果：取ret和[left,right]区间的最大值
时间复杂度：O(N)。空间复杂度：O(1)。
class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.size();int hash[128] = { 0 };int left = 0, right = 0;int ret = 0;while(right < n){hash[s[right]]++;//进窗口while(hash[s[right]] > 1)//判断{hash[s[left++]]--;//出窗口}ret = max(ret,right - left + 1);right++;}return ret;}
};3.最大连续1的个数（三）
1004. 最大连续1的个数 III - 力扣（LeetCode）
思路：滑动窗口
1、定义左右指针left，right，0的计数器zero。
2、进窗口，nums[right]如果是1，无视，如果是0，计数器+1
3、判断zero的个数是否大于k，大于则出窗口（nums[left]如果是1无视，如果是0，zero--）
4、更新结果
class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n = nums.size();int ret = 0;for(int left = 0, right = 0, zero = 0; right < n; right++){if(nums[right] == 0)//进窗口zero++;while(zero > k)//判断{if(nums[left++] == 0)//出窗口zero--;}ret = max(ret, right - left + 1);}return ret;}
};4. 将x减到0的最小操作数
1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）
思路：如果直接考虑这个问题会很复杂，所以正难则反，直接考虑将中间段的数求和等于 target（总和 - x），最后再用总长度 - 中间段长度的最大值，就是要求的两端的最小值。这样思路就和第一道题一样。还是以滑动窗口的思路。
- 定义左右指针left，right
- 进窗口
- 如果滑动窗口中的总值 大于 target 出窗口
- 当窗口中的总值等于target时更新ret
class Solution
{
public:int minOperations(vector<int>& nums, int x) {int n =nums.size();int sum = 0;for(int i = 0; i < n; i++){sum += nums[i];}int target = sum - x;if(target < 0)//数组中都是正整数，如果减出小于0的数，那么直接返回-1就行return -1;int count = 0,ret = -1;for(int left = 0, right = 0; right < n; right++){count += nums[right];//进窗口while(count > target)//判断{count -= nums[left++];//出窗口}if(count == target){ret = max(ret,right - left + 1);//更新结果，要ret的最大值}}return ret == -1 ? -1 : n - ret;}
};5.水果成篮
904. 水果成篮 - 力扣（LeetCode）
解决思路： 滑动窗口+哈希
进窗口：将fruits的右指针指向的值放入hash中
判断：当hash中的值（种类）超过两个，就开始出窗口
出窗口：直接将hash中fruits的左指针指向的值--。然后判断这个值在hash中是否还存在，不存在就直接删除这个hash[friuts[left]]。
最后更新结果。
class Solution
{
public:int totalFruit(vector<int>& fruits) {unordered_map<int ,int> hash;int n = fruits.size();int ret = 0;for(int left = 0, right = 0; right < n; right++){hash[fruits[right]]++;//进窗口while(hash.size() > 2)//判断{hash[fruits[left]]--;//出窗口if(hash[fruits[left]] == 0)hash.erase(fruits[left]);left++;}ret = max(ret, right - left + 1);//更新结果}return ret;}
};因为这个代码大量使用了哈希的删除，会导致用时增加，题目中给了这个水果的种类不会超过100000种，所以我们也可以直接使用哈希数组来解决，再增加一个kinds来记录哈希数组中水果的种类。
class Solution
{
public:int totalFruit(vector<int>& fruits) {int hash[100001] = { 0 };int n = fruits.size();int ret = 0;for(int left = 0, right = 0, kinds = 0; right < n; right++){if(hash[fruits[right]] == 0)kinds++;//用kinds来记录水果种类hash[fruits[right]]++;//进窗口while(kinds > 2)//判断{hash[fruits[left]]--;//出窗口if(hash[fruits[left]] == 0)kinds--;left++;}ret = max(ret, right - left + 1);}return ret;}
};6.找到字符串中所以字母异位词
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
解决思路：滑动窗口，p子串的大小是固定的，相当于一个p长度大小的窗口在s中滑动，定义两个哈希数组，一个存储p中字符的出现次数，另一个存储窗口中字符的出现次数，再定义一个count来存储窗口中的有效字符。
进窗口：将right对应的字符放入hash2中，进入后如果是有效字符，并且数量小于等于p中hash的数量，就++count。
判断：当窗口大小大于p的长度就开始出窗口。
出窗口：先判断出窗口的值是否是有效的字符，是有效字符就count--，然后再出窗口。
最后当窗口中的有效字符等于p的长度，就是最终结果
class Solution
{
public:vector<int> findAnagrams(string s, string p) {int hash1[26] = { 0 };int hash2[26] = { 0 };vector<int> ret;int m = p.size();for(auto e : p){hash1[e - 'a']++;//将p的值存入hash1中}//count存当前窗口有效字符的个数for(int left = 0, right = 0, count = 0; right < s.size(); right++){hash2[s[right] - 'a']++;//进窗口if(hash2[s[right] - 'a'] <= hash1[s[right] - 'a'])//当进窗口后的字符是有效字符，count++count++;if(right - left + 1 > m)//判断{if(hash2[s[left] - 'a'] <= hash1[s[left] - 'a'])//当出窗口前是有效字符count--count--;hash2[s[left] - 'a']--;//出窗口 left++;}if(count == m)ret.push_back(left);}return ret;}
};7.串联所有单词的子串
438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
思路：这个题的思路和上一道题思路一样，还是滑动窗口+哈希表，只是上个题是字符，这个题是字符串， 不同的点是
1.哈希表是unordered_map<string,int>。
2.指针移动的步长是words中单词的长度。
3.还需要增加滑动窗口的执行次数。
所以hash2得定义到循环中，每次执行不同的滑动窗口的时候要用到不同的hash2。
若 hash2 定义在循环外会导致的问题
-
数据污染
当处理完偏移量i=0后，hash2会保留窗口中的单词频次。当处理i=1时，这些残留数据会导致：- 单词频次统计错误（包含前一轮的数据）
count计数器失效（累计了无效计数）
class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {unordered_map<string, int> hash1;//保存words里面所以单词的频次vector<int> ret;for(auto &e : words){hash1[e]++;} int len = words[0].size();int m = words.size();for(int i = 0; i < len; i++)//执行len次，因为words字符串出现的地方不一定是len整数倍的地方{unordered_map<string, int> hash2;//维护窗内单词的频次for(int left = i, right = i, count = 0; right + len <= s.size(); right += len){string in = s.substr(right, len);hash2[in]++;//进窗口if(hash2[in] <= hash1[in])count++;if(right - left + 1 > len * m)//判断{string out = s.substr(left, len);if(hash2[out] <= hash1[out])count--;hash2[out]--;//出窗口left += len;}if(count == m){ret.push_back(left);}}}return ret;}
};8.最小覆盖子串
76. 最小覆盖子串 - 力扣（LeetCode）
思路：滑动窗口+哈希表
遍历t字符串，用kinds来记录t中的种类，用count来记录窗口中的有效种类，用begin和minlen来记录要返回的子串的开始位置和长度。
进窗口：还是直接将right所指向的值放入hash2中，因为count记录的是窗口中的有效种类，所以判断进窗口后hash1和hash2对应的值相对的话有效种类count++。
判断：当满足条件时出窗口。
更新结果：窗口区间小于minlen时就更新minlen和begin。
出窗口：出窗口前先判断hash1和hash2对应的值是否相等，相等的话就--count。再出窗口
class Solution {
public:string minWindow(string s, string t) {int kinds = 0;int hash1[128] = { 0 };int hash2[128] = { 0 };for(auto e : t){if(hash1[e] == 0)kinds++;hash1[e]++;}int begin = -1, minlen = INT_MAX;for(int left = 0, right = 0, count = 0; right < s.size(); right++){hash2[s[right]]++;if(hash2[s[right]] == hash1[s[right]])count++;//count记录窗口中有效的种类。while(count == kinds){if(right - left + 1 < minlen){minlen = right - left + 1;begin = left;}if(hash2[s[left]] == hash1[s[left]])count--;hash2[s[left]]--;left++;}}if(begin == -1)return "";elsereturn s.substr(begin, minlen);}
};
