题目
给你一个整数数组 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;
}
}