Leetcode复习小结: Sliding Window

已经很久没有更新了，目前的刷题状况是：已经做了600+道题，基本覆盖所有常见类型，拿到一道题一般有思路或者大致的方向，easy和偏简单的median基本没问题，难度较大的题目做不做得出来主要看类型。contest从一开始的一两道甚至一道都做不出到现在三道甚至四道（题目比较简单常规时）。但是回过头去看做过的这些题水分还是有的，做过的题做不出来或者有思路写不出bug free的代码是常有的事情，所以新开了一个section按tag重刷一遍，尤其是高频。之后复习完每个专题会来这边简单地写写小结，希望别坑掉。

Sliding Window
Sliding Window的本质：对于每一个尾指针j，使用移动头指针i的方式，求以j结尾的满足条件的最长或最短的subarray。时间复杂度一般为O(N)，因为头指针i和尾指针j只能move forward,不能backward。
当题目要求最长或最短的subarray时考虑用sliding window，看对于每一个以j结尾的subarray，头指针i是否只能向前移动，如果是的可以用sliding window解决，如果i可以向后移动就考虑其他解法。典型的题目如：

340 Longest Substring with At Most K Distinct Characters
这两道都用的是HashMap+count
992 Subarrays With K Different Integers：这道题是340的拓展，关键在于：
exactly(K) = most(K) - most(K-1)
424 Longest Repeating Character Replacement

还有一种sliding window是移动一个固定长度的窗口，例如
567 Permutation in String：HashMap+count
239 Sliding Window Maximum
1100 Find K-Length Substrings With No Repeated Characters
480 Sliding Window Median
这一类的题目都是考虑一个“进出”的问题，窗口每移动一个单位，就把最左边不在窗口里的删掉，把最右边的加进窗口中

还有一些没有归类到Sliding Window，但个人觉得用到了Sliding Window思想的题目：
795. Number of Subarrays with Bounded Maximum

Subarray sum
看到和subarray sum相关的题目，第一反应是从prefix sum入手。虽然切入点都是prefix sum，但具体处理起来方法很多
560 Subarrays sum equal to K：求和为K的subarray的个数。用HashMap存储distinct prefix sum和其个数
1074 Number of Matrix that sum to target: 560的延伸，从一维到二维。基本方法还是一样的，重点是如何将二维数组压缩成一维数组。具体实现我会在二维数组部分进行总结（如果我真的写了的话。。。）
209.subarray sum equals k:给一个正数数组，求使得和>=s的最短subarray的长度。这道题有一种O(N)解法和一种O(NlogN)的解法。O(N):Sliding window, O(NlogN): TreeMap/Binary Search，这里TreeMap记录的是前缀和和其index
ps: 这道题里所有数都是正数，如果会出现负数怎么处理呢？
这就是862. Shortest Subarray with Sum at Least K，需要用到deque，和Sliding Window Maximum解法比较类似，本质是monotonic queue，关于这个问题之后有空再总结