【Leetcode】327. 区间和的个数（困难）

给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。

区间和 S(i, j)表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

示例1：

输入：nums = [-2,5,-1], lower = -2, upper = 2
输出：3
解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。

示例2：

输入：nums = [0], lower = 0, upper = 0
输出：1

提示：

• 1 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105
• − 2 31 < = n u m s [ i ] < = 2 31 − 1 -2^{31} <= nums[i] <= 2^{31} - 1 −231<=nums[i]<=231−1
• − 1 0 5 < = l o w e r < = u p p e r < = 1 0 5 -10^5 <= lower <= upper <= 10^5 −105<=lower<=upper<=105
• 题目数据保证答案是一个 32 位 的整数

class Solution {
public:
    int countRangeSum(vector& nums, int lower, int upper) {

    }
};

327. 区间和的个数

  （1）如果暴力解决，时间复杂度为 O ( N 3 ) O(N^3) O(N3)，因为子数组的数量为 O ( N 2 ) O(N^2) O(N2)，而遍历验证这些子数组的和的时间复杂度为 O ( N ) O(N) O(N)，所以总的时间复杂度为 O ( N 3 ) O(N^3) O(N3)
  （2）优化1：利用前缀和数组，则不用遍历验证子数组的和，时间复杂度就变成 O ( N 2 ) O(N^2) O(N2)
  （3）优化2：任何一个子数组都会以某个位置结尾，如果以 i i i 位置结尾的子数组达标的个数为 a a a 个，以 j j j 位置结尾的子数组达标的个数为 b b b 个，那么最终结果为每个位置结尾的子数组达标的个数之和（即先求以每个位置结尾的子数组和的达标个数）
  （4）如果 s u m ( i . . . j ) sum(i...j) sum(i...j) 累加和在 [lower, upper] 范围上，那么 s u m ( 0... j ) − s u m ( 0... i − 1 ) sum(0...j) - sum(0...i - 1) sum(0...j)−sum(0...i−1) 也在这个范围上。

   举例：数组 arr(0…17)，要求的范围为 [10, 40]，那么求以 17 这个位置为结尾的子数组和落在 [10，40] 这个范围上的个数。
   假设 arr(0…17) 的前缀和为 100，则现在问题转化为之前有多少个前缀和是落在 [100 - upper, 100 - lower] = [60, 90] 这个范围上。

   总结来说就是假设 0 ~ i i i 整体累加和是 x x x，题目的目标是 [ l o w e r , u p p e r ] [lower, upper] [lower,upper]，思路转化为求必须以 i i i 位置结尾的子数组有多少个在 [ l o w e r , u p p e r ] [lower, upper] [lower,upper] 范围上 等同于 求 i i i 之前所有前缀和中有多少个前缀和在 [ x − u p p e r , x − l o w e r ] [x - upper, x - lower] [x−upper,x−lower] 上

   原始数组 nums 处理成前缀和数组 sum，求 sum 数组中的每个数 x 之前有多少个数落在 [x - upper, x - lower] 范围上，怎么求呢？用归并排序。

  在合并左右组的时候，针对右组的每个元素 num，左组有多少个数是落在 [num - upper, num - lower] 范围上的。

   O ( N l o g N ) O(N logN) O(NlogN)

class Solution {
public:
    int merge(vector &sum, int left, int mid, int right, int lower, int upper) {
        //1. 不merge，但是对于右组中的每个数x，求左组中有多少个数，位于[x - upper, x - lower]
        //核心技巧：不回退
    	//比如假设右组是[7,13,29,30,31]，而原始目标是[5,10]范围，
    	//那么右组的每个元素，依次要在左组中找的元素的范围为[-3, 2] [3, 8] [19, 24]...
    	//可以发现，每个数的下限和上限都不会回退（相等或递增），因为越来越大的数字在减去同一个[lower, upper]
    	//在左组中滑动 l 和 r，保证l滑动到的位置数字 >= x - upper，r滑动到的位置数字 <= x-lower
    	//因为窗口不回退，所以时间复杂度为O(N)

        //winL和winR都是左组数据的滑动窗口
        int cnt = 0;
        int winL = left;
        int winR = left; 
        //因为winL和winR都是不回退的，所以整体时间复杂度为O(n)
        for (int i = mid + 1; i <= right; i++) {
            //针对右组的数，左组的数应该在范围[mim, max]
            long max = sum[i] - lower;
            long min = sum[i] - upper;

            while (winR <= mid && sum[winR] <= max) { //winR滑动一直到所在位置的数大于max，不包含该位置
                winR++;
            }

            while (winL <= mid && sum[winL] < min) { //windowL滑动一直到所在位置的数不小于min，包含该该位置
                winL++;
            }
            cnt += winR - winL; //(windowR - 1) - windowL + 1 = windowR - windowL 就是左组中满足当前选择的右组元素的需要范围的[min, max]个数
        }

        //2. 正常merge
        int p1 = left;
        int p2 = mid + 1;
        vector help(right - left + 1);
        int ind = 0;
        while (p1 <= mid && p2 <= right) {
            help[ind++] = sum[p1] <= sum[p2] ? sum[p1++] : sum[p2++];
        }

        while (p1 <= mid) {
            help[ind++] = sum[p1++];
        }

        while (p2 <= right) {
            help[ind++] = sum[p2++];
        }

        for (int i = 0; i < help.size(); i++) {
            sum[left + i] = help[i];
        }

        return cnt;
    }
	//nums[L...R] 已经不传进来了，只传进来sum（前缀和数组） 
	//求sum[L...R]中，有多少个子数组累加和在[lower, upper]上
    int process(vector &sum, int left, int right, int lower, int upper) {
    	//代表原始数组arr[0...L] 范围的累加和sum[L]， 如果这个值在[lower, upper]范围上，说明子数组[0...L]是符合要求的
        if (left == right) {
        	//返回1表示0...L 这个数组是一个符合要求的数组
            return sum[left] >= lower && sum[right] <= upper ? 1 : 0;
        }

        int mid = left + ((right - left) >> 1);

        int leftCnt = process(sum, left, mid, lower, upper);
        int rightCnt = process(sum, mid + 1, right, lower, upper);
        int mergeCnt = merge(sum, left, mid, right, lower, upper);

        return leftCnt + rightCnt + mergeCnt;
    }

    int countRangeSum(vector& nums, int lower, int upper) {
        if (nums.size() == 0) return 0;

        //前缀和数组
        vector sum(nums.size(), 0);
        sum[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            sum[i] = sum[i - 1] + nums[i];
        }

        return process(sum, 0, sum.size() - 1, lower, upper);
    }
};

1. 利用前缀和搞事情
2. 原数组在范围 [lower, upper] 转化为 前缀和数组中 x 求 [x - upper, x - lower] 的问题
3. 前缀和数组 x 之前有多少个数是落在新的范围上
4. 放到归并排序中去处理
5. merge过程必须达到时间复杂度 O ( N ) O(N) O(N)， 这就要求找到不回退的技巧