力扣 327：区间和的个数（归并排序解）

题目描述

给定一个数组arr，两个整数lower和upper，返回arr中有多少个子数组的累加和在[lower,upper]范围上

思路分析

大体思路：

我们用以i结尾的子数组来划分整个数组，例如：0-i, 1-i, 2-i......，现在我们只需要统计这些以i结尾的子数组中，有多少个满足条件即可（i= 0, 1, 2, ..., n)
我们用前缀和数组sum来代替原数组arr做分析，转化为：求以当前i结尾的子数组中有多少个在[lower,upper]范围上，就是求sum[0] -> sum[i]有多少落在[cur-upper, cur-lower]上

因为arr[j] -> arr[i]的和实际上等于sum[i] - sum[j]
接下来就是实现merge函数，现在前缀和数组从mid隔开，分为左右两组，两组都有序，由于已经求得左组和右组分别的计数，现在只需要求左右两组构成的大组的计数即可

具体代码：

java

// 给定一个数组arr，两个整数lower和upper，
// 返回arr中有多少个子数组的累加和在[lower,upper]范围上
public static int countRangeSum(int[] arr, int lower, int upper) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    long[] sum = getSum(arr);
    return process(sum, 0, arr.length - 1, lower, upper);
}

java

// 求前缀和数组：sum[i] 位置代表 arr[0] -> arr[i] 的和
public static long[] getSum(int[] arr) {
    long[] sum = new long[arr.length];
    sum[0] = arr[0];
    for (int i = 1; i < arr.length; i++) {
        sum[i] = sum[i - 1] + arr[i];
    }
    return sum;
}

现在的目标：统计以i结尾的子数组（0->i, 1->i, ...）的和满足条件的个数

转换为：依次以sum[i] = cur为基准，求sum[0] -> sum[i]有多少落在[cur-upper, cur-lower]上

假如sum[j]落在[cur-upper, cur-lower]上，说明arr[j] -> arr[i]的和落在 [lower, upper]上

解释：arr[j] -> arr[i]的和实际上等于sum[i] - sum[j]

java

// 分析至此我们可以不用arr数组来处理了，就可以使用前缀和sum数组
public static int process(long[] sum, int l, int r, int lower, int upper) {
    // 这里判断了sum[i]落在[cur-upper, cur-lower]上的特殊情况，也就是l==r
    if (l == r) {
        if (sum[l] >= lower && sum[l] <= upper) return 1;
        else return 0;
    }
    int mid = l + ((r - l) >> 1);

    return process(sum, l, mid, lower, upper) +
            process(sum, mid + 1, r, lower, upper) +
            merge(sum, l, mid, r, lower, upper);
}

merge方法的具体逻辑：

1：

先不排序，先计数

我们现在的目标：右组各个i结尾的子数组，有多少个数组的和满足条件

现在数组从mid隔开，分为左右两组，两组都有序

回忆要求的过程：依次以sum[i] = cur为基准，求sum[0] -> sum[i - 1]有多少落在[cur-upper, cur-lower上

因此我们以右组为基准，指针cur指向mid + 1开始处理

cur代表当前处理的sum[i]，目标：看左组有几个sum[j]落在[cur-upper, cur-lower]上

用一个滑窗（两个指针windowL, windowR表示范围），每当cur移动时，附带着windowL和windowR的移动

windowL移动：当cur移动后，找到第一个 >= min 的位置 windowR移动：当cur移动后，找到第一个 > max 的位置

解释：windowL和windowR都不需要回退，因为有序，sum[cur] - upper或lower一定增大

也就是说，当前上下限的补一定增大

所以windowL和windowR都应该右移，也变大直到满足范围

滑窗所包含n个数就是当前满足的个数

2：归并排序的过程

java

// merge方法：mid隔开的左右两部分已经有序
// 现在在merge方法中对整个数组进行计数并排序
public static int merge(long[] sum, int l, int mid, int r, int lower, int upper) {

	// 1
    int windowL = l;
    int windowR = l;
    int cur = mid + 1;
    int rst = 0;

    while (cur <= r) {
        long curMin = sum[cur] - upper;
        long curMax = sum[cur] - lower;
        while (windowL <= mid && sum[windowL] < curMin) {
            windowL++;
        }
        while (windowR <= mid && sum[windowR] <= curMax) {
            windowR++;
        }
        rst += windowR - windowL;
        cur++;
    }

    // 2
    long[] help = new long[r - l + 1];
    int p1 = l;
    int p2 = mid + 1;
    int idx = 0;
    while (p1 <= mid && p2 <= r) {
        help[idx++] = sum[p1] <= sum[p2] ? sum[p1++] : sum[p2++];
    }

    while (p1 <= mid) {
        help[idx++] = sum[p1++];
    }
    while (p2 <= r) {
        help[idx++] = sum[p2++];
    }

    for (int i = 0; i < help.length; i++) {
        sum[l + i] = help[i];
    }
    return rst;
}

对数器验证

java

public static int comparator(int[] arr, int lower, int upper) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int count = 0;
    for (int i = 0; i < arr.length; i++) {
        long sum = 0;
        for (int j = i; j < arr.length; j++) {
            sum += arr[j];
            if (sum >= lower && sum <= upper) {
                count++;
            }
        }
    }
    return count;
}

public static int[] generateRandomArray(int maxSize, int maxValue) {
    int size = (int) (Math.random() * (maxSize + 1));
    int[] arr = new int[size];
    for (int i = 0; i < size; i++) {
        arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
    }
    return arr;
}

public static void main(String[] args) {
    int testTime = 500000;
    int maxSize = 100;
    int maxValue = 100;
    boolean succeed = true;
    System.out.println("测试开始");
    for (int i = 0; i < testTime; i++) {
        int[] arr = generateRandomArray(maxSize, maxValue);
        int lower = (int) (Math.random() * 201) - 100;
        int upper = lower + (int) (Math.random() * 101);
        int ans1 = countRangeSum(arr, lower, upper);
        int ans2 = comparator(arr, lower, upper);
        if (ans1 != ans2) {
            succeed = false;
            System.out.println("出错了!");
            System.out.println("arr: " + Arrays.toString(arr));
            System.out.println("lower: " + lower + ", upper: " + upper);
            System.out.println("你的答案: " + ans1);
            System.out.println("正确答案: " + ans2);
            break;
        }
    }
    if (succeed) {
        System.out.println("测试结束，通过！");
    }
}