5.8/5.9滑动窗口专题（leecode209，leecode643，leecode1695，leecode3, leecode159）

leecode209. 长度最小的子数组

滑动窗口呢，说白了也是双指针问题

class Solution {
public:
    int minSubArrayLen(int target, vector& nums) {
        int front_index = 0;
        int end_index = 0;
        int result = 1e9;
        while(end_index < nums.size() && front_index <= end_index){
            if(sum(nums, front_index,end_index) < target){
                end_index++;
            }

            else if(sum(nums, front_index, end_index) >= target){
                result = min(result, end_index - front_index + 1); 
                front_index++;
            }

        }
        if(result == 1e9) return 0;
        else return result;
    }

    int sum(vector& nums, int begin, int end){
        int sum = 0;
        for(int i = begin; i <= end; i++){
            sum+=nums[i];
        }

        return sum;
    }
};

下面的方法省掉了sum函数。

class Solution {
public:
    int minSubArrayLen(int target, vector& nums) {
        int result = 1e9;
        int sublength = 0;
        int i = 0;
        int sum = 0;
        //初始化后指针j
        for(int j = 0; j < nums.size(); j++){
            sum+=nums[j];
            //这里要注意，只有sum>=target的时候才会执行，如果一直不执行，result恒等于1e9，
            //所以最后出结果的时候要进行判断
            while(sum >= target){
                sublength = j - i + 1;
                result = min(sublength, result);
                sum-=nums[i++];

            }
        }
        
        return result == 1e9 ? 0 : result;
    }

    
};

双指针法，直接秒杀

class Solution {
public:
    double findMaxAverage(vector& nums, int k) {
        double result = -1e9; // 因为有负数，所以这么写
        //平均值最大，意味着和最大
        double average = 0;
        double sum = 0;
        int i = 0;
        for(int j = 0; j < nums.size(); j++){
            sum+=nums[j];
            while(j-i+1==k){
                average = sum/(j-i+1);
                result = max(result, average);
                sum-=nums[i++];
            }
        } 

        return result;
    }
};

class Solution {
public:
    int maximumUniqueSubarray(vector& nums) {
       int l = 0;
       int r = 0;
       int sum = 0;
       int ans = 0;
       map cnt;
       for(r; r < nums.size(); r++){
           cnt[nums[r]]++;
           //如果发现重复元素,就把做指针想右边移动，因为重复的数字一定是新进窗口的数字
           //所以判断cnt[nums[r]]是否大于1
           while(cnt[nums[r]] > 1){
               cnt[nums[l]]--;
               sum -= nums[l];
               l++;
           }
           sum += nums[r];
           ans = max(ans, sum);

       }

       return ans;
    }

};

此题用滑动窗口也可直接秒杀
这道题目其实跟leecode3如出一辙，但是这道题我在写的时候出了点小问题,我最开始的代码如下

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int cnt[26] = {0};
        int l = 0;
        int r = 0;
        int sub = 0;
        int ans = 0;
        if(s.length() == 0) return 0;
        else{
        for(r; r < s.length(); r++){
            cnt[s[r]-'a']++;
            while(cnt[s[r] - 'a'] > 1){
                cnt[s[l]-'a']--;
                l++;
                sub = r - l + 1;
            }
            sub = r - l + 1;
            ans = max(sub, ans);
        }

        return ans;
        }
    }
};

但是这种代码会报错，但输入是" “的时候，因为我只判断了当字符串长度为0时的情况，如果输入是” "的时候，cnt数组的索引会为负数。会出现如下错误

所以为了防止负数索引的出现，我建议使用map一一映射来存储26个字母出现的顺序

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map cnt;
        int l = 0;
        int r = 0;
        int sub = 0;
        int ans = 0;
        if(s.length() == 0 || s.empty()) return 0;
        else{
        for(r; r < s.length(); r++){
            cnt[s[r]]++;
            while(cnt[s[r]] > 1){
                cnt[s[l]]--;
                l++;
                sub = r - l + 1;
            }
            sub = r - l + 1;
            ans = max(sub, ans);
        }

        return ans;
        }
    }
};

但是我们已经知道测试用例里用的ascll码中最小的为char = ’ '。所以我们可以采用以下索引，这样就不会出现错误

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int cnt[100] = {0};
        int l = 0;
        int r = 0;
        int sub = 0;
        int ans = 0;
        if(s.length() == 0 || s.empty()) return 0;
        else{
        for(r; r < s.length(); r++){
            cnt[s[r]-' ']++;
            while(cnt[s[r]-' '] > 1){
                cnt[s[l]-' ']--;
                l++;
                sub = r - l + 1;
            }
            sub = r - l + 1;
            ans = max(sub, ans);
        }

        return ans;
        }
    }
};

同样使用双指针算法，注意这里，map和unordered_map的时间复杂度并不一样。map是logn，unordered_map则是1，所以键值对储存可以使用unordered_map

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        int l = 0;
        int r = 0;
        int sub = 0;
        int ans = 0;
        unordered_map cnt;
        for(r; r < s.size(); r++){
            cnt[s[r]]++;
            //至多包含两个，那就是说当字符串中有三个一样的元素时候，left指针就要向左移动
            while(cnt.size() >= 3){
                cnt[s[l]]--;
                if(cnt[s[l]] == 0){
                    cnt.erase(s[l]);
                }
                
                l++;
                sub = r - l + 1;
            }

            sub = r - l + 1;
            ans = max(sub, ans);
        }

        return ans;
    }
};