滑动窗口例题讲解

1.长度最小的子数组

本题暴力解法就是双层for循环，遍历子序列的首位结点，然而滑动窗口却仅仅遍历尾指针。从0开始遍历尾指针，头指针不动，sum记录当前序列的总数，直到满足题目条件（sum>target)开始往右移动头指针，以寻找题目要求的更短子序列，直到不符合要求。此时继续执行外层循环，即向右移动尾指针，以寻找下一个符合要求的子序列。找到之后再移动头指针，以寻找题目要求的更短子序列，直到不符合要求。依次类推。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum = 0,i = 0;
        int result = INT_MAX;
        for(int j = 0;j < nums.size();j ++){
        	sum += nums[j];
        	while(sum >= target){
        		if((j - i + 1) < result){
        			result = j - i + 1;
				}
				sum -= nums[i];
				i ++;
			}
		}
		
		return result == INT_MAX ? 0 : result;
    }
};

理解之后把此题代码作为模板，看接下来两道题

2.水果成篮

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int a[100010] = {0}; // 用于记录每种水果的数量
        int cnt = 0;  // 当前种类数
        int result = 0;  // 最大长度
        int i = 0;  // 左指针
        for (int j = 0; j < fruits.size(); j++) {
            if (a[fruits[j]] == 0) {
                cnt++;  // 如果是新加入的水果种类，种类数加1
            }
            a[fruits[j]]++;  // 增加该水果种类的数量

            // 如果种类数小于等于2，则继续扩展窗口
            while (cnt > 2) {
                a[fruits[i]]--;  // 将左指针指向的水果移出窗口
                if (a[fruits[i]] == 0) {
                    cnt--;  // 如果水果种类数量为0，种类数减1
                }
                i++;  // 移动左指针
            }

            // 更新最大结果
            result = max(result, j - i + 1);
        }
        return result;  // 返回最大长度
    }
};

【【小白都能听懂的算法课】【力扣】【LeetCode 76】最小覆盖子串｜滑动窗口｜字符串】https://www.bilibili.com/video/BV1sJ4m1g727?vd_source=e583d26dc0028b3e6ea220aadf5bc7fe

本题的不同之处就是要判断子序列何时满足条件，可以建立一个映射关系：首先对t字符频率进行统计，比如样例，t中A有1个，B有1个，C有1个，若是s中的一个子序列的A，B，C的数量分别大于等于t中A，B，C的数量时，此时的子序列就是符合要求的，可以继续进行右移头指针和进行其他操作。

s = "ADOBECODEBANC", t = "ABC"

class Solution {
public:
    string minWindow(string s, string t) {
    	
    	
        int a[200] = {0};//记录s 
        int b[200] = {0};//记录t 
        int have = 0,cnt = 0;
        //初始化t字符串，记录其每个字符出现的次数和数量 
        for(int i = 0;i < t.size();i ++){
        	if(b[t[i]] == 0)cnt ++;
        	b[t[i]] ++; 
		}
		
		int resStart = 0, resLens = INT_MAX;
		int i = 0;
		
		for(int j = 0;j < s.size();j ++){
			if(b[s[j]] != 0){
				a[s[j]] ++;
				if(a[s[j]] == b[s[j]])have ++;
			}
			
			while(have == cnt){
				if(j - i + 1 < resLens){
					resLens = j - i + 1;
					//substr(start,lens)
					resStart = i;
				}
				
				if(b[s[i]] != 0){
					a[s[i]] --;
					if(a[s[i]] < b[s[i]]){
						have --;
					}
				} 
				
				i ++;
				
			}
			
		}
		
		return resLens == INT_MAX ? "" : s.substr(resStart,resLens);
		
    }
};