区间和的个数

package class05;

/**
 * 区间和的个数
 * <p>
 * https://leetcode.com/problems/count-of-range-sum/
 * 给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数。
 * 区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。
 */
public class Code01_CountOfRangeSum {
    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; i++) {
            //前缀和数组中，arr[i]等于，原数组nums[0]-nums[i]的累加和。
            //也就是原数组nums中，它(sum[i])前面所有数的累加和，再加上它自己。
            sum[i] = sum[i - 1] + nums[i];
        }
        return process(sum, 0, sum.length - 1, lower, upper);
    }

    private static int process(long[] sum, int L, int R, int lower, int upper) {
        //在判断(子数组1-子数组2)在不在[lower, upper]上时，
        //当子数组2是空数组，即一个元素也没有时，也就是子数组1就是整个数组本身时：
        if (L == R) {
            //如果是真，就返回有一个达标的数组。否则，就返回没有达标的数组。
            return sum[L] >= lower && sum[L] <= upper ? 1 : 0;
        }
        int M = L + ((R - L) >> 1);
        int process1 = process(sum, L, M, lower, upper);
        int process2 = process(sum, M + 1, R, lower, upper);
        int merge = merge(sum, L, M, R, lower, upper);
        return process1
                + process2
                + merge;
    }

    //合并
    private static int merge(long[] sum, int L, int M, int R, int lower, int upper) {
        int ans = 0;
        int windowL = L;
        int windowR = L;
        //窗口范围是：[windowL, windowR)
        //从右组中开始，也就是从M+1位置开始。
        for (int i = M + 1; i <= R; i++) {
            //使用前缀和，分解原问题。
            //区间和 S(i, j)，相当于是：sum[j]-sum[i-1]，即(sum[0]~sum[j])-(sum[0]~sum[i-1])。
            //原问题：求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数。
            long min = sum[i] - upper;
            long max = sum[i] - lower;
            while (windowR <= M && sum[windowR] <= max) {//当sum[windowR]大于max时，跳出。
                windowR++;
            }
            while (windowL <= M && sum[windowL] < min) {//当sum[windowL]等于min时，跳出。
                windowL++;
            }
            //此时的[windowL, windowR)上的每一个数，都是达标的数字。
            //因为sum是前缀和数组，不是原数组nums，所以sum中的每一个数字，就代表一个区间和。并且是从0到当前索引位置。
            ans += windowR - windowL;//每次merge，累加上ans。每次merge，累加上ans。最后ans就是所有达标的对数之和。
        }
        //经典归并排序：
        long[] help = new long[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = M + 1;
        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 ans;
    }

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

    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    public static void main(String[] args) {
        int maxSize = 100;
        int maxValue = 100;
        int testTimes = 100000;
        System.out.println("test start!");
        for (int i = 0; i < testTimes; i++) {
            int lower;
            int upper;
            do {
                lower = (int) (Math.random() * maxValue);
                upper = (int) (Math.random() * maxValue);
            } while (lower > upper);
            int[] arr0 = generatorRandomArray(maxSize, maxValue);
            int[] arr1 = copyArray(arr0);
            int[] arr2 = copyArray(arr0);
            int res = countRangeSum(arr1, lower, upper);
            int test = test(arr2, lower, upper);
            if (res != test) {
                System.out.println("oops!");
                break;
            }
        }
        System.out.println("test end!");
    }

    //暴力解法
    public static int test(int[] arr, int lower, int upper) {
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                int ans = 0;
                for (int m = i; m <= j; m++) {
                    ans += arr[m];
                }
//                System.out.print(ans + " ");
                if (ans >= lower && ans <= upper) {
                    count++;
                }
            }
//            System.out.println();
        }
//        System.out.println("count = " + count);
        return count;
    }

}
/*
 * 提示：
 * 假设0-i整体的累加和是x，
 * 求以i位置结尾的所有的子数组中，有多少个在[lower, upper]上，
 * 等同于去求，i之前的所有前缀和中，有多少个前缀和，在[x-upper, x-lower]上。
 *
 * 小结：
 * 1.前缀和可以做一些事情。
 * 2.将原问题转换成，另一个问题，即原数组中，值位于[x-upper, x-lower]上的区间和的个数。(x是前缀和sum中的某一个值)
 * 原问题：求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数。
 * 3.前缀和中，x之前，有多少个数，在[x-upper, x-lower]上。
 * 4.在归并排序的过程中做这些事。
 * 5.要想merge左组和右组，是O(N)的时间复杂度，必须知道p1，p2不回退的技巧。
 */