归并排序面试题——区间和的个数

题目

给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的区间和的个数 。区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

力扣链接：区间和个数

前置知识

前缀和：

sum[i...j]=arr[0...j]-arr[0...i-1]

准备一个前缀和数组presum，长度和原数组长度一样。如下图：

问题转换

1.假设0~i位置整体累加和是X，求必须以i位置结尾的子数组，有多少个在[lower,upper]，就等同于去求，i之前的所有前缀和中有多少前缀和在[X-upper,X-lower]上

2.原数组[lower,upper] —> 前缀和数组中的每一个X 求[X-lower,X-upper]

3 . 传进来的每一个前缀和数组 有多少个落在[X-lower,X-upper]

4 . 放在归并排序里面求

代码：

package com.harrison.class03;

/**
 * @author Harrison
 * @create 2022-02-24-22:01
 * @motto 众里寻他千百度，蓦然回首，那人却在灯火阑珊处。
 */
public class Code05_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++){
            sum[i]=sum[i-1]+nums[i];
        }

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

    // arr[L...R]已经不传进来了，只传进来sum（前缀和数组！！！）
    // 求在原始数组arr[L...R]中，有多少个子数组累加和在[lower,upper]上
    public static int process(long[] sum, int L, int R, int lower, int upper){
        if(L==R){
            return sum[L]>=lower && sum[L]<=upper?1:0;
        }
        // L!=R 范围上不止一个位置
        int M=L+((R-L)>>1);
        return process(sum,L,M,lower,upper)+
                process(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 ans=0;
        int windowL=L;
        int windowR=L;
        // [windowL,windowR)
        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++;
            }
            ans+=windowR-windowL;
        }
        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;
    }
}