满足某个条件的连续区间——滑动窗口法

基本思路

如果想要在一段连续序列中找到一段符合某个条件的连续序列，暴力解法可以从每个元素开始逐步增长序列往后找，由于满足条件与否与一个序列相关，那么如果能避免每次都重新开始找，记录一部分结果，效果显然会好一点：

#include<iostream>
#include<vector>
using namespace std;

//滑动窗口法可以处理对一段连续数组区间的判断
//这个判断是固定的，和当前这段连续数组有关，要么为真要么为假
//那么是否能判断完全部的区间呢？
//如果我们要找的是满足某个条件的连续数组区间，是可以的
//从某个位置开始，一直找到满足条件的区间的末位置
//然后再从这个位置开始走，节省的是嵌套循环O（n^2)中内部循环逐步累加的过程

//计算复杂度，前后两个指针都要走完整个数组 2n
//前面一个走一下判断一下，后面一个走一下判断一下，判断次数 2n
//总体是O（n）的计算复杂度


//判断条件是连续数组子序列元素和是否大于等于s
int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }

int main(){
    vector<int> test={1,2,1,3,4,2,4,5};
    cout<<minSubArrayLen(8,test)<<endl;
}

变式

满足条件的最长的连续序列

需要把区间移动的条件，和记录最值得位置做一点调整：

/*
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。



示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。
示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

*/
#include<iostream>
#include<vector>
#include<map>
using namespace std;

//判断条件是连续数组子序列元素数目
int maxSubArrayLenElemNumLimit(int limit, vector<int>& nums) {
        int result = 0;
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        int elemType=0;
        map<int,int> elemNum;

        for (int j = 0; j < nums.size(); j++) {
            // 新增一个后端元素时，判断条件的变化
                //如果元素不存在，新增map，改变元素计数值
                if(elemNum.find(nums[j])==elemNum.end()){
                    elemNum[nums[j]]=1;
                    elemType++;
                }else{//如果元素存在，在map中记录元素个数变化
                    elemNum[nums[j]]++;
                }

                if(elemType<=limit){
                    subLength = (j - i + 1); // 取子序列的长度
                    result = result > subLength ? result : subLength;
                }

                // 使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
                //条件是当元素个数太多，慢指针要走到直至元素个数不超
                while (elemType>limit) {//满足条件时，慢指针移动 
                    //减少一个前端元素，判断条件的变化   
                    elemNum[nums[i]]--;
                    if(elemNum[nums[i]]==0){
                        elemNum.erase(nums[i]);
                        elemType--;
                    }  
                    i++;
                }   

        }
        // 如果result没有被赋值的话，就返回说明没有符合条件的子序列
        return result == 0 ? -1 : result;
    }

int main(){
    vector<int> test={3,3,3,1,2,1,1,2,3,3,4};
    cout<<maxSubArrayLenElemNumLimit(2,test)<<endl;
}

复杂些的判断条件

#include<iostream>
#include<vector>
#include<string>
#include<map>
using namespace std;

/*
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。


示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。
示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
*/
//滑动窗口法可以处理对一段连续数组区间的判断
//这个判断是固定的，和当前这段连续数组有关，要么为真要么为假
//那么是否能判断完全部的区间呢？
//如果我们要找的是满足某个条件的连续数组区间，是可以的
//从某个位置开始，一直找到满足条件的区间的末位置
//然后再从这个位置开始走，节省的是嵌套循环O（n^2)中内部循环逐步累加的过程

//计算复杂度，前后两个指针都要走完整个数组 2n
//前面一个走一下判断一下，后面一个走一下判断一下，判断次数 2n
//总体是O（n）的计算复杂度




string minSubStringCover(string base,string cover_limit){
    //把需要覆盖的字符记到哈希表
    map<char,int> need_cover_chars;
    map<char,int> chars_count;
    for(int i=0;i<cover_limit.size();i++){
        if(need_cover_chars.find(cover_limit[i])!=need_cover_chars.end()){
            need_cover_chars[cover_limit[i]]++;
        }else{
            need_cover_chars[cover_limit[i]]=1;
            chars_count[cover_limit[i]]=0;
        }
    }

    //初始化滑动窗口前端，子串长度，结果记录的序列变量
    int i=0;
    int subLength=0;
    int resultLen=INT32_MAX;
    int resultI=0;
    int resultJ=0;
    int coveredFlag;

    //开始滑动窗口检查
    for(int j=0;j<base.size();j++){
        //新增后端元素时处理
        if(need_cover_chars.find(base[j])!=need_cover_chars.end()){
            chars_count[base[j]]++;
        }


        coveredFlag=1;
        for (map<char, int>::iterator it = need_cover_chars.begin(); it != need_cover_chars.end(); ++it) {
                if (it->second > chars_count[it->first]){
                    coveredFlag=0;
                }
        }

        //条件是，map中的每个元素都不为0
        while(coveredFlag==1){
            //记录最小区间
            subLength = (j - i + 1); // 取子序列的长度
            if(resultLen>subLength){
                resultLen=subLength;
                resultI=i;
                resultJ=j;
            }

            //减少前端元素的处理
            if(need_cover_chars.find(base[i])!=need_cover_chars.end()){
                chars_count[base[i]]--;
            }
            i++;
            //重新计算是否满足条件
            coveredFlag=1;
            for (map<char, int>::iterator it = need_cover_chars.begin(); it != need_cover_chars.end(); ++it) {
                    if (it->second > chars_count[it->first]){
                        coveredFlag=0;
                    }
            }
        }
    }

    string ans="";
    cout<<resultI<<" "<<resultJ<<endl;

    if(resultLen!= INT32_MAX) {
        for(int i=resultI;i<=resultJ;i++){
            ans+=base[i];
        }
    }

    return ans;

}


int main(){

    string s="a", t = "aa";
    cout<<minSubStringCover(s,t)<<endl;
}