prefix sum

xxx[xxxxxx]xxxxxxx
简单来说，prefixsum的问题一般都是问能不能求一个连续subarray，使得这个subarray有某种特质，比如sum等于某个target，还问有几个这样的subarray,还会问最长的sum==target的subarray的长度，525,560,930,1983. 还有神奇的问题是，能不能找到三个点，使得这个subarray分成四份，每份sum（不包含三个点）都相等548.简单的问法是能不能分成两份一样的，不包含这个点734。求出除了这个点之外的其他所有点的乘积。求这个subarray的sum能被k整除523,974。


如果最长的或者最短的使得这个subarray的和能不能>=target（正数）. 这样就比较危险了，你要时刻注意，这个数组是全部正数，还是有负数。209,962,862,1124
209 最短：如果数组里的数字都是正数，反而好办。[[x[xxxx]xx]xx 从[开始一直走到]，好不容易使得[]里的sum>=target,那么有没有可能[]>=target，不可能,他们只会更小。有没有可能[]>=target,可能，所以这个是two pointer+presum.
862 最短，有负数，难点。xx[x[x[x]，对于]来说，所有前面[，都可能使得[]>=target.  假设维持递增序列12345，下一个数如果是6，那么尽可能选q前几个，使得6-1>=k.6后面又来了个7，我们也不会再需要用到1，因为61的距离小于71的距离。假设维持递增序列12345，下一个数字是3，那么我们需要345吗，不需要。所以q的前面后面都可以删除。deque做了这道题，太难了。
962，找到使得后面数字比前面大的最长的长度.对于每个数字来说，其实都是再前面所有数字里面从前往后找，找到第一个比它小的数字。321，45.        对于5，我们找了123.对于4我们无论怎么找，都不可能找到比53更长的。
962只是为了1124做准备，因为他问的是最长的subarray sum>=1.但是因为1124里的元素求presum[i]时候，都是比presum[i-1]多一或者少一，所以只要找到第一个出现presum[i]-1的位置就可以了。它是一个962的特殊例子。
https://docs.google.com/presentation/d/1ITl7JuZOlhRG0hgICIAQuD3zJn-fE5PZ9IjV97PZwLQ/edit?usp=sharing