Leetcode中和Subarray-Sum相关的小结

虽然之前在 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 貌似都不可用上述方法解。