个人主页 ： zxctscl
专栏 【C++】、 【C语言】、 【Linux】、 【数据结构】、 【算法】
如有转载请先通知

前言

1 209. 长度最小的子数组

1.1 分析

暴力枚举出所有的子数组和，发现可以利用双指针来解决。
这里双指针是同向的，就能优化为滑动窗口。
(1)先初始化left和right，用left和right来标记这个窗口的左右区间
(2)进窗口
(3)判断决定是否出窗口

1.2 代码

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums){int n=nums.size();int sum=0,len=INT_MAX;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==INT_MAX?0:len;}
};

2 3. 无重复字符的最长子串

2.1 分析

暴力枚举利用双指针加哈希表：
left在起始位置，right遍历，当字符不在哈希表里，就添加；当字符在时候，right就停止遍历，把此时的字符长度更新一下；再把left移动到与right遍历到相同字符的那个位置的后面一个，然后right再继续移动。

使用滑动窗口来实现：

(1)先初始化left和right，用left和right来标记这个窗口的左右区间
(2)进窗口，让字符进入哈希表
(3)判断：当窗口内出现重复字符出窗口，再从哈希表中删除该字符。
再更新长度

2.2 代码

class Solution 
{
public:int lengthOfLongestSubstring(string s) {int hash[128]={0};//数组模拟哈希表int n=s.size();int ret=0;for(int left=0,right=0;right<n;right++){hash[s[right]]++;//进窗口while(hash[s[right]]>1)//判断{hash[s[left++]]--;//出窗口}ret=max(ret,right-left+1);}return ret;}
};

3 1004. 最大连续1的个数 III

3.1 分析

只要翻转的0个数小于等于k就行。
如果按照题目要求翻转，是比较麻烦的，但可以等价处理为：找一个区间满足0的次数不超过k就行。
也就是找出最长子数组，这个子数组的0不超过k个
解法一：暴力枚举所有子数组，加上一个计数器zero
优化一下

固定left，right向后移动，right遇到0统计一个计数器，计数器等于3时候，停止枚举，就是这个区间最优解。

利用滑动窗口来解决问题：

1. 先定义两个指针left=0,right=0
2. 进窗口，如果right遇到1，无视；遇到0，zero+1
3. 判断：zero>k 就 出窗口
   判断完后更新结果

3.2 代码

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int ret=0;for(int left=0,right=0,zero=0;right<nums.size();right++){if(nums[right]==0)zero++;while(zero>k)if(nums[left++]==0)zero--;   ret=max(ret,right-left+1);}return ret;}
};

4 1658. 将 x 减到 0 的最小操作数

4.1 分析

发现既有左边删除，又有右边的的，不好操作，此时可以找一个连续区域，恰好所有元素的和(sum)等于sum-x

1. 先定义两个指针left=0,right=0
2. 进窗口，sum+=nums[right]
3. 判断：sum>target
   出窗口：sum-=nums[left]
   当sum==target判断完后更新结果

4.2 代码

class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum=0;for(int a:nums)sum+=a;int target=sum-x;if(target<0)return -1;int ret=-1;for(int left=0,right=0,tmp=0;right<nums.size();right++){tmp+=nums[right];while(tmp>target){tmp-=nums[left++];}if(tmp==target)ret=max(ret,right-left+1);}if(ret==-1)return -1;else{return nums.size()-ret;}}
};

5 904. 水果成篮

5.1 分析

题目意思就是：找出一个最长子数组，子数组中不超过两种类型的水果。

解法一：暴力枚举+哈希表：从某一个位置开始，建立一个哈希表，暴力枚举时候，遍历一个放哈希表一个，当表中数据超过2时候，就出现了多余水果，前面的区间就是最优解。

优化：固定一个位置left，right遍历数组放在哈希表中，直到某一个位置，right再向右遍历时候，水果种类就超过2，此时这段区间就是最优解。此时，当left向后移动一位时，种类数目（kinds)可能会出现两种情况：（1）kinds不变，那么right也不变；（2）kinds变小,此时right就可以向右移动

解法二：滑动窗口

1. 先定义两个指针left=0,right=0
2. 进窗口，遍历数组放哈希表里，哈希表里面放水果种类及对应数量
3. 判断：如果哈希表长度大于2而且它对应数量为0时候就出窗口
   更新结果
   

5.2 代码

class Solution {
public:int totalFruit(vector<int>& fruits){int hash[100001]={0};int ret=0;for(int left=0,right=0,kinds=0;right<fruits.size();right++){if(hash[fruits[right]]==0)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. 找到字符串中所有字母异位词

6.1 分析

如何快速判断两个字符串是否是异位词？
两个字符串的构成是一样的，利用哈希表，遍历两个字符串分别放在哈希表中，对比两个哈希表中字符出现的个数是否相等就行，相等就是，反之就不是。

算法：
暴力+哈希表
把p字符串先放入哈希表中，再到s中找相等长度的区间子串放在另一个哈希表中，比较一个，相等就把起始位置放在结果中。

当s中与p等长区间中比较后，不是异位词，此时就把s放在哈希表中的第一个字符删除，再加上区间长度下一个位置字符就行。

p长度为m，hash1记录p的字符情况，hash2记录s中一段区间的字符情况
滑动窗口+哈希表

1. 先定义两个指针left=0,right=0
2. 进窗口，(哈希表遍历s)hash2[in]++
3. 判断：right-left+1>m，就出窗口，再hash1[out]–（对应s中的字符得删除）

当两个哈希表里面存在信息是否一致时候，就更新结果

优化：更新判断条件
利用变量count来统计窗口中有效字符的个数
right遍历时候，c加入哈希表2中，与hash1中c个数相比较，都是1，此时count=1；
right继续向后面移动，遇到c加入hash2中，这个时候hash2中c=2，,比hash1中c=1大，这个时候count不更新；
right继续向后移动，b放入hash2中，比较hash1中b=1，此时count=2，而且s遍历的区间长度等于p的长度，此时有效字符个数count=2不等于p的长度；
right继续右移，这是区间长度大于p的，left就右移，a放到哈希表2中a=1，count=3，删除c（hash2中c=2，删除的这个c是无效字符），hash2中c=1；

进窗口：进窗口后比较hash2[in]<=hash1[in]此时count++;
出窗口：出去前 hash2[out]<=hash1[out]此时count–;
更新结果：count=m

6.2 代码

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int hash1[26]={0};//统计pfor(auto x:p)hash1[x-'a']++;int hash2[26]={0};//sint m=p.size();for(int left=0,right=0,count=0;right<s.size();right++){char in=s[right];hash2[in-'a']++;if(hash2[in-'a']<=hash1[in-'a'])count++;if(right-left+1>m){char out=s[left++];if(hash2[out-'a']<=hash1[out-'a'])count--;hash2[out-'a']--;}if(count==m)ret.push_back(left);}return ret;}
};

7 30. 串联所有单词的子串

7.1 分析

与上面串联所有单词的子串类似，只不过把字符换成字符串，解法类似。
把题目给的words中的字符串看做一个一个整体，像下面这样

与上面不同的是：
（1）哈希表：不能向上面一样用数组来实现，这里存字符串，得用unordered_map<string,int> hash
（2）left与right指针的移动：移动的步长是单词的长度(len)
（3）滑动窗口指向的次数：单词可能是从s的第一个位置开始划分，也可能是第二个位置，也可能是第三个位置：

滑动窗口执行len次

7.2 代码

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string,int> hash1;for(auto& x:words)hash1[x]++;int len=words[0].size(),m=words.size();for(int i=0;i<len;i++){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);//进窗口+维护counthash2[in]++;if(hash2[in]<=hash1[in])count++;//判断if(right-left+1>len*m){//出窗口+维护countstring 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. 最小覆盖子串

8.1 分析

与串联所有单词的子串类似，

解法一：暴力枚举+哈希表
在连续区间中找符合要求的ABC出现次数

在符合连续区间中，left右移right会出现两种情况

解法二：滑动窗口

1. 先定义两个指针left=0,right=0
2. 进窗口，hash2[in]++
3. 判断：对比一下hash2有效字符大于等于hash1有效字符就更新结果起始位置，最短长度；再出窗口，hash2[out]–

优化：利用变量count来统计窗口中有效字符的种类
（1）.进窗口 进之后当hash2[in]==hash1[in]此时count++
（2） 出窗口 出之前，当hash2[out]==hash1[out]，count--
（3）判断 count==hash.size()

8.2 代码

class Solution {
public:string minWindow(string s, string t) {int hash1[128]={0};int kinds=0;//统计有效字符有多少种for(auto& x:t){if(hash1[x]==0) kinds++;hash1[x]++;}int hash2[128]={0};int minlen=INT_MAX,begin=-1;for(int left=0,right=0,count=0;right<s.size();right++){char in=s[right];hash2[in]++;if(hash2[in]==hash1[in])count++;//进窗口+维护countwhile(kinds==count){if(right-left+1<minlen){minlen=right-left+1;begin=left;}char out=s[left++];if(hash2[out]--==hash1[out])count--;}}if(begin==-1)return "";else return s.substr(begin,minlen);}
};