刷题类型总结

让自己永远在输出！
类型一：

1. Pattern: Sliding window，滑动窗口类型
   滑动窗口类型的题目经常是用来执行数组或是链表上某个区间（窗口）上的操作。比如找最长的全为1的子数组长度。滑动窗口一般从第一个元素开始，一直往右边一个一个元素挪动。当然了，根据题目要求，我们可能有固定窗口大小的情况，也有窗口的大小变化的情况。
   窗口滑动示意图
   
   代表类型题目包括：

Maximum Sum Subarray of Size K (easy)

Smallest Subarray with a given sum (easy)

Longest Substring with K Distinct Characters (medium)

Fruits into Baskets (medium)

No-repeat Substring (hard)

Longest Substring with Same Letters after Replacement (hard)

Longest Subarray with Ones after Replacement (hard）

一天刷个easy+medium；hard的一天一个哦~

2020.4.9-2020.4.14，完成上述的刷题~

// 第二题求解，使用了双端队列，自己想了半天实现的代码思路过于复杂（并且没有实现出来），参考别的解法，发现自己写的有问题。
//而且该方法不是用滑动窗口解的，如果数组全部为正可以用滑动窗口解，这里先借鉴一下！
//解题思路比较简单，首先将数组里面的元素求和，然后与最小的相减，和次小的相减。。。最后找到符合要求的即可。
//我自己的思路是设立一个数组，数组的内容每次都是滑动窗口相加的结果，然后再与K相比较，这样时间复杂度和空间复杂度都很大，不好用！
class Solution {
public:
    int shortestSubarray(vector<int>& A, int K) {
        
        int n = A.size();
        vector<int> sum(n+1, 0);
        
        for(int i = 0; i < n; i++) 
            sum[i+1] = sum[i] + A[i];
        
        deque<int> de;
        int j = 0;
        int res = n+1;
        
        while(j<=n){
            
            while(!de.empty() && sum[j] <= sum[de.back()]){ 
                de.pop_back();
            }
            while(!de.empty() && sum[j] - sum[de.front()] >= K){ 
                res = min( res, j - de.front());
                de.pop_front();
            }
            de.push_back(j); 
            j++;
        }
        if(res == n+1)
            return -1;
        else
            return res;
    }
};