Subarray Sum Equals K
思路
对于这种给定k值找subarray的问题，我们有一个统一的解法，那就是prefix sum + 哈希。比如说我们要去找sum = 0的subarray，然后说prefix[3] = 6, prefix[8] = 6, 因为6-6=0，所以我们知道array[4,8]是一个合法解。
不过这个算法有一个情况不能覆盖，那就是当prefix subarray sum = 0，这时候我们没有短数组可以被减。这时我们可以通过一个小技巧来walkaround,那就是在traversal之前，在HashMap.put(0, -1)，表示空数组的情况，这样我们就可以保证永远都有的减了。
步骤
在traversal里面，每次visit一个新的element的时候：
- update preifxSum
- 使用prefixSum比较b-a的逻辑
- insert prefixSum into HashMap
题型变种
找subarray sum = 定值k, 那么使用HashMap
- 如果题目要求的只是某一个sum = k的subaray，那么HashMap的key记录的是sum value，value记录的是index。
- 如果题目要求的是返回所有sum = k的subarray的数量，那么HashMap的key记录的是sum value，value记录的是frequency。这样每次后面再遇到sum一样的subarray的时候，所有之前已经出现过的subarray都可以和他形成一个合法解。
- 如果题目要求返回的是所有sum = k的具体subarray，那么HashMap的key记录的是sum value，value记录的是a list of index。这样每次后面遇到sum一样的subarray的时候，所有之前已经出现过的subarray都可以和他形成一个合法解。
- 如果题目找到的Maximum Size Subarray Sum Equals k并且可能包含负数，那么我们就不能使用双指针了，还是要想到subarray sum equals k的解法，这里因为要找最大的size，所以如果我们遇到一个prefix sum已经在HashMap里，我们就不要去更新了。
找subarray sum closet to k，那么使用TreeMap
- 如果题目要求的是closest sum的subarray，那么此时我们应该replace HashMap with TreeMap，其余的都不变。
找subarray sum within range [a,b]，那么使用prefixSum + Binary Search in sorted array
- 如果题目要找sum 在interval [a,b]之间的subarray的数量，那么这时候我们要进行的操作是range query，但是BST不适合binary search range query，我们还得转化成sorted array然后二分求解。
找submatrix sum = 定值k, 那么使用column prefixSum
- 如果题目要找submatrix sum = 0, 那么我们要使用column prefixSum来把整个matrix转化回一个array来看待。比如Leetcode 363. Max Sum of Rectangle No Larger Than K
题目
- Lintcode 138. Subarray Sum
- Lintcode 139. Subarray Sum Closest
- Lintcode 404. Subarray Sum II
- Lintcode 405. Submatrix Sum
- Leetcode 325. Maximum Size Subarray Sum Equals k
- Leetcode 363. Max Sum of Rectangle No Larger Than K
- Leetcode 327. Count of Range Sum (这道题和Subarray Sum II非常像，都是求subarray sum在interval区间里，区别是那道题所有的element都是非负的，所以我们在)