327. Count of Range Sum

class Solution { private: int countHelper(vector<long>&sum,int start,int end,int lower,int upper) { if(end-start<=1)//sum个数小于等于1无法求范围 return 0; int mid=(start+end)/2; int count=countHelper(sum,start,mid,lower,upper)+countHelper(sum,mid,end,lower,upper); vector<long> cache(end-start,0); int k=mid;//第一个sum[k]-sum[i]>=lower int j=mid;//第一个sum[j]-sum[i]>upper int t=mid;//sum[t]<sum[i]; int len=0; for(int r=0,i=start;i<mid;i++) { while(k<end&&sum[k]-sum[i]<lower)k++; while(j<end&&sum[j]-sum[i]<=upper)j++; count+=(j-k);//更新count while(t<end&&sum[t]<sum[i])cache[r++]=sum[t++]; cache[r++]=sum[i]; len=r; } for(int i=0;i<len;i++) { sum[start+i]=cache[i]; } return count; } public: int countRangeSum(vector<int>& nums, int lower, int upper) { if(nums.size()==0) return 0; vector<long> sum(nums.size()+1,0); for(int i=1;i<=nums.size();i++) { sum[i]=sum[i-1]+nums[i-1]; } return countHelper(sum,0,nums.size()+1,lower,upper); } };