专题二：滑动窗口【优选算法】

滑动窗口：

什么时候用？ 同向双指针（找单调性）

怎么用？

1）用left、right指针维护窗口

2）进窗口（right指针++，更新窗口内的值）

3）判断

出窗口（left++，并更新窗口内的值）

4）更新结果（注意每道题更新结果的时机不同，需具体分析）

滑动窗口：

1、长度最小的子数组

2、无重复字符的最长子串

3、最大连续1的个数

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

5、水果成篮

6、找到字符串中所有字母异位词

7、串联所有单词的子串(容器的使用）

8、最小覆盖子串

1、长度最小的子数组

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int sum = 0,len = INT_MAX;
        for(int l = 0,r = 0;r < n;r++){
            sum += nums[r];//入窗口
            while(sum >= target)//判断
            {
                len = min(len,r - l + 1);//更新结果
                sum -= nums[l++];//出窗口
            }
        }    
        return len == INT_MAX?0:len;    
    }
};

2、无重复字符的最长子串

暴力解法，枚举每一个字串，但分析可发现，出现重复字符时，left可直接跳到重复字符，right也无需往回走。因此就是同向双指针，也就是滑动窗口。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> hash(128);//用来判断字符是否出现过
        int len = 0,n = s.size();
        for(int l = 0,r = 0;r < n;r++){//进窗口
            hash[s[r]]++;
            while(hash[s[r]] > 1)//判断
            {
                hash[s[l]]--;//出窗口
                l++;
            }
            len = max(len,r-l+1);//更新结果
        }
        return len;
    }
};

3、最大连续1的个数

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size();
        int count = 0;
        int ret = 0;
        for(int left = 0,right = 0;right < n;right++){//进窗口
            if(nums[right] == 0) count++;
            while(count > k)//判断
                if(nums[left++] == 0)count--;//出窗口
            ret = max(ret,right-left+1);//更新结果
        }
        return ret;
    }
};

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

通过正难则反，可以将此题转换成类似第一题

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int n = nums.size();
        int sum = 0;
        for(auto x : nums){
            sum += x;
        }
        int target = sum - x;

        if(target < 0) return -1;
        int ret = -1,sum2 = 0;
        for(int left = 0,right = 0;right < n;right++){
            sum2 += nums[right];
            while(sum2 > target) sum2 -= nums[left++];
            if(sum2 == target) ret = max(ret,right - left + 1);
        }
        return ret == -1?-1:n - ret;
    }
};

5、水果成篮

unordered_map版

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int,int> hash;
        int n = fruits.size();
        int kind = 0,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;
    }
};

数组版：

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int hash[100010] = {0};
        int n = fruits.size();
        int kind = 0,ret = 0;
        for(int left = 0,right= 0;right < n;right++){
            if(hash[fruits[right]] == 0) kind++;
            hash[fruits[right]]++;

            while(kind > 2)
            {
                hash[fruits[left]]--;
                if(hash[fruits[left]] == 0) kind--;
                left++;
            }
            ret = max(ret,right - left + 1);
        }
        return ret;
    }
};

6、找到字符串中所有字母异位词

check的优化：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int hashp[265] = {0};
        for(auto x : p) hashp[x]++;
        int count = 0;
        vector<int> ret;
        int hashs[256] = {0};
        for(int l = 0,r = 0;r < s.size();r++){
            hashs[s[r]]++;
            if(hashs[s[r]] <= hashp[s[r]]) count++;
            if(r - l + 1 > p.size())
            {
                if(hashs[s[l]] <= hashp[s[l]]) count--;
                hashs[s[l]]--;
                l++;
            }
            if(count == p.size()) ret.push_back(l);
        }
        return ret;
    }
};

7、串联所有单词的子串(容器的使用）

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

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = {0};
        int kinds = 0;//统计有效字符种类数

        for(auto ch : t) 
        {
            if(hash1[ch] == 0) kinds++;
            hash1[ch]++;
        }
        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++;
            while(count == kinds)
            {
                if(right - left+1 < minlen)
                {
                    minlen = right - left + 1;
                    begin = left;
                }
                char out = s[left++];
                if(hash2[out] == hash1[out]) count--;
                hash2[out]--;
            }
        }
        if(begin == -1) return "";
        else return s.substr(begin,minlen);
    }
};