3、滑动窗口
209. 长度最小的子数组
题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3] 输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4] 输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0
思路分析
方法一:暴力法
使用两个for循环,依次判断寻找最小的子序列
方法二:滑动窗口法
所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
算法步骤:
使用两个变量i,j分别表示窗口的两个边界.
当窗口内的值< target时,右边界j进行后移,直至>=target.此时就是以i为左边界的窗口,且满足条件—是最小的子序列.
然后i继续后移,寻找其他最小的窗口,对比判断选择更加符合题意的.
这里还是以题目中的示例来举例，s=7， 数组是 2，3，1，2，4，3，来看一下查找的过程：
参考代码
暴力法
//方法一:暴力解法 int minSubArrayLen(int target, vector<int>& nums) { int result = INT_MAX; int str_len = 0;//子序列长度 int sum = 0;//子序列的和 for(int i = 0; i < nums.size(); i++) { sum = 0; for(int j = i; j < nums.size(); j++) { sum+=nums[j]; if(sum>=target) { str_len = j-i+1; result = result>=str_len?str_len :result ; break;//找到了则一定要break一下.因为需要的是最小长度. } } } result = result==INT_MAX ? 0 : result;//如果没有找到, 则result赋值为0 return result; }
双指针法
int minSubArrayLen(int target, vector<int>& nums) { int i = 0,j = 0,res =INT_MAX ,sum = 0,subLength;//sum:窗口的值 subLength: 滑动窗口的长度 for(j = 0; j<nums.size(); j++) { sum+=nums[j];//如果不满足条件,则不断增大窗口的右边界. while(sum>=target) { subLength = j-i+1; res = min(res,subLength);//更新窗口的大小值 sum -= nums[i++];//如果满足,则减小窗口.==>窗口右移动,即起始位置后移. } } if (res!=INT_MAX) { return res; } else {//如果没有找到, 则result赋值为0 return 0; } }
904. 水果成篮
题目描述
树由整数数组fruits表示，其中水果[i]是第i棵树产生的水果类型。
你想收集尽可能多的水果。但是，所有者有一些严格的规则，您必须遵守：
你只有两个篮子，每个篮子只能装一种水果。每篮水果的数量没有限制。
从您选择的任何一棵树开始，您必须在向右移动时从每棵树（包括起始树）中恰好摘下一个水果,摘下的水果必须放在你的一个篮子里。 一旦你到了一棵树上，树上的果实没法放入你的篮子（两个篮子已经满了），你必须停下来。
给定整数数组水果，返回可以拾取的最大水果数。
本题，其实就是 选只有两个元素的最长连续子序列，比如1，2，3，2，2最长就是2，3，2，2（只包括2或者3，而且是最长的）。
示例 1：
输入：[1,2,1] 输出：3
解释：我们可以收集 [1,2,1]。
示例 2：
输入：[0,1,2,2] 输出：3
解释：我们可以收集 [1,2,2]
如果我们从第一棵树开始，我们将只能收集到 [0, 1]。
示例 3：
输入：[1,2,3,2,2] 输出：4
解释：我们可以收集 [2,3,2,2]
如果我们从第一棵树开始，我们将只能收集到 [1, 2]。
示例 4：
输入：[3,3,3,1,2,1,1,2,3,3,4] 输出：5
解释：我们可以收集 [1,2,1,1,2]
如果我们从第一棵树或第八棵树开始，我们将只能收集到 4 棵水果树。
思路分析
使用i,j分别指向窗口的左右两端.
窗口的右边界开始后移直到窗口内元素的个数大于2,
然后左窗口进行右移动,直到窗口内只有两种元素.
然后更新最大的水果树.最终进行返回.
参考代码
//这个相比上个题,从对窗口内值的约束变为了 类型数 的约束 int totalFruit(vector<int>& fruits) { map<int,int> window; int k = 2;//类型数 int i = 0,j,res = 0;//i:窗口左边界 for(j = 0; j < fruits.size(); j++) { window[fruits[j]]++;//向窗口中添加元素 while(window.size()>k) { //如果当前窗口中元素类型的个数大于k ,则想办法减小到k window[fruits[i]]--; if(window[fruits[i]]==0) { window.erase(fruits[i]);//如果个数为空,移除元素 } i++;//每一次while,窗口左下标右移动 } //更新res res = max(res,j-i+1); } return res; }
76. 最小覆盖子串
题目描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC"
示例 2：
输入：s = "a", t = "a" 输出："a"
示例 3:
输入: s = "a", t = "aa" 输出: ""
解释: t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
思路分析
方法一:滑动窗口法
滑动窗口的思想：
用i,j表示滑动窗口的左边界和右边界，通过改变i,j来扩展和收缩滑动窗口，可以想象成一个窗口在字符串上游走，当这个窗口包含的元素满足条件，即包含字符串T的所有元素，记录下这个滑动窗口的长度j-i+1，这些长度中的最小值就是要求的结果。
1.步骤一
不断增加j使滑动窗口增大，直到窗口包含了T的所有元素
2.步骤二
不断增加i使滑动窗口缩小，因为是要求最小字串，所以将不必要的元素排除在外，使长度减小，直到碰到一个必须包含的元素，这个时候不能再扔了，再扔就不满足条件了，记录此时滑动窗口的长度，并保存最小值
3.步骤三
让i再增加一个位置，这个时候滑动窗口肯定不满足条件了，那么继续从步骤一开始执行，寻找新的满足条件的滑动窗口，如此反复，直到j超出了字符串S范围。
面临的问题：
如何判断滑动窗口包含了T的所有元素？??
我们用一个vector need / map来表示当前滑动窗口中需要的各元素的数量，一开始滑动窗口为空，用T中各元素来初始化这个need，当滑动窗口扩展或者收缩的时候，去维护这个need，例如当滑动窗口包含某个元素，我们就让need中这个元素的数量减1，代表所需元素减少了1个；当滑动窗口移除某个元素，就让need中这个元素的数量加1。
记住一点：need始终记录着当前滑动窗口下，我们还需要的元素数量，我们在改变i,j时，需同步维护need。
值得注意的是，只要某个元素包含在滑动窗口中，我们就会在need中存储这个元素的数量，如果某个元素存储的是负数代表这个元素是多余的。比如当need等于{‘A’:-2,‘C’:1}时，表示当前滑动窗口中，我们有2个A是多余的，同时还需要1个C。这么做的目的就是为了步骤二中，排除不必要的元素，数量为负的就是不必要的元素，而数量为0表示刚刚好。
回到问题中来，那么如何判断滑动窗口包含了T的所有元素？
结论就是当need中所有元素的数量都小于等于0时，表示当前滑动窗口不再需要任何元素。
优化
如果每次判断滑动窗口是否包含了T的所有元素，都去遍历need看是否所有元素数量都小于等于0，这个会耗费O(k)的时间复杂度，k代表need长度，最坏情况下，k可能等于len(S)。
其实这个是可以避免的，我们可以维护一个额外的 变量needCnt来记录所需元素的总数量，当我们碰到一个所需元素c，不仅need[c]的数量减少1，同时needCnt也要减少1，这样我们通过needCnt就可以知道是否满足条件，而无需遍历整个数组了。
前面也提到过，need记录了遍历到的所有元素，而只有need[c]>0大于0时，代表c就是所需元素
参考代码
string minWindow(string s, string t) { vector<int> need(128,0);// 65 97 用来保存需要的字符以及个数 for(char ch : t) {//初始化 need[ch]++; } int j, i ,result = INT_MAX,str_len,start = 0;// start记录满足条件窗口的起始位置 int cnt = t.size();//还需要的字符个数 for(j = 0,i = 0; j < s.size(); j++) {//j相当于快指针,i相当于慢指针 char ch = s[j]; if(need[ch]>0) { cnt--; } need[ch]--;//右边的字符加入窗口 if(cnt==0) { //窗口一定包含所需要的全部字符 while(i<j&&need[s[i]]<0) { //排除不必要的字符 need[s[i++]]++; } str_len = j-i+1; if(str_len < result) { //更新result和start result = str_len; start = i; } need[s[i++]]++;//左边界继续右移动,寻找下一个窗口. cnt++; //需要的目标字符进行增加变成1 } } return result == INT_MAX ? "" : s.substr(start,result) ; }
