虽然之前在Sliding Window那篇小结里总结了一些关于subarray sum的题目，但总觉得还不够系统所以打算花更大的篇幅对leetcode中涉及到subarray sum的题目做一个小结。
1. 求subarray sum的最大值
53 Maximum Subarray:一道非常经典的dp题，这里就不作总结了
2. 求满足条件的subarray sum的个数
560. Subarray Sum Equals K:
求subarray sum等于K的subarray的个数，这里用HashMap记录每个前缀和的个数，和元素的正负无关。
那如果不是要求相等，而是要求>=或<=K的个数呢（当然>或<也是一样的，这里仅用>=和<=做例子）？
（1）如果所有元素均为正数：
印象中并未在leetcode中见过完全一样的题目，不过应该有一些类似的题目。总而言之都是用sliding window来处理，复杂度：O(N) O(1)。既然leetcode中没找到，那就自己写吧：
求一个正数数组中>=K的subarray sum的个数
public int countSubarray(int[] nums, int k) { for int count = 0, sum = 0, l = 0; for (int r = 0; r < nums.length; r ++) { sum += nums[r]; while (sum >= K) sum -= nums[l++]; count += l; } return count;}求一个正数数组中<=K的subarray sum的个数
public int countSubarray(int[] nums, int k) { int count = 0, sum = 0, l = 0; for (int r = 0; r < nums.length; r ++) { sum += nums[r]; while (sum > k) sum -= nums[l++]; count += r - l + 1; } return count;}（2）如果去掉均为正数的限制，数组中正负数都有可能出现
327. Count of Range Sum
和之前的题目相比，难度陡增，这道题merge sort/BIT/Segment Tree都可以解决，本质都是divide and conquer。复杂度：O(NlogN) O(1)个人更倾向于merge sort的解法（其实是因为对BIT/Segment Tree用得不熟）
3.求满足条件的subarray sum的最短/最长length
用hashmap记录prefix sum和index的关系，index是该prefix sum首次出现的位置。如果题目改成minimum size subarray sum equals k，那么hashmap中就改成记录index最近出现的位置。这道题同样和正负无关
非相等情况：
（1）如果元素均为正数
求一个正数数组中subarray sum >= k的最小长度
求一个正数数组中subarray sum <= k的最大长度
public int maxLength(int[] nums, int k) { int sum = 0, max = 0, l = 0; for (int r = 0; r < nums.length; i ++) { sum += nums[r]; while (sum > k) sum -= nums[l++]; max = Math.max(r-l+1, max); } return max;}(2) 如果元素可能存在负数
862. Shortest Subarray with Sum at Least K
难度提高一个档次，用sliding window + monotonic queue解决
如果题目改成shortest + at most k，longest + at least k, longest + at most k貌似都不可用上述方法解。