LeetCode 327. 区间和的个数 (前缀和 / 归并排序 / hard难度)

1. 前缀和 + 归并排序

因为归并后原顺序不变，并且因为归并过程中左右都是保持有序的，所以区间会不断推进，不会有重复的情况，时间复杂度也是O(n)的。

2. 有序表 (后续补充)

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public static int countRangeSum(int[] nums, int lower, int upper) {
        if (nums == null || nums.length == 0) return 0;

        // 求前缀和
        long[] sum = new long[nums.length];
        sum[0] = nums[0];
        for (int i = 1; i <= nums.length - 1; i++) {
            sum[i] = sum[i - 1] + nums[i];
        }

        return count(sum, 0, sum.length - 1, lower, upper);
    }

    // 根据传入前缀和数组，在原始的nums[L,R]中，有多少子数组累加和在[lower， upper]
    public static int count(long[] sum, int L, int R, int lower, int upper) {
        // 这一步专门用来计算 0 ~ 当前数前缀和是否符合的
        if (L == R) {
            return sum[L] >= lower && sum[L] <= upper ? 1 : 0;
        }

        int M = L + ((R - L) >> 1);

        // 计算左右部分归并，以及当前次归并时统计的个数
        return count(sum, L , M , lower, upper) + 
        	   count(sum, M + 1, R, lower, upper) + 
        	   merge(sum, L , M , R, lower, upper);
    }

    public static int merge(long[] sum, int L, int M, int R, int lower, int upper) {
        // 先计算区间和个数
        int res = 0;
        int windowL = L;
        int windowR = L;
        for (int i = M + 1; i <= R; i++) {
            long min = sum[i] - upper;
            long max = sum[i] - lower;
            while (windowR <= M && sum[windowR] <= max) {
                windowR++;
            }
            while (windowL <= M && sum[windowL] < min) {
                windowL++;
            }
            // 形成的区间为 [L,R) 左闭右开
            res += (windowR - windowL);
        }

        // 在进行归并排序
        long[] help = new long[R - L + 1];
        int p1 = L;
        int p2 = M + 1;
        int i = 0;

        while (p1 <= M && p2 <= R) {
            help[i++] = sum[p1] <= sum[p2] ? sum[p1++] : sum[p2++];
        }

        while (p1 <= M) {
            help[i++] = sum[p1++];
        }
        while (p2 <= R) {
            help[i++] = sum[p2++];
        }
        for (i = 0; i < help.length; i++) {
            sum[L + i] = help[i];
        }

        return res;
    }

}
//leetcode submit region end(Prohibit modification and deletion)