力扣每日一题——327.区间和的个数

原题链接

题目描述

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

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

例如：

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

思路求解

这是一道困难题,所以知识点综合的当然有点多,没事,我们来一步步的分析

首先,我们当然有暴力的方法来找答案,(用两个指针一前一后维护子数组然后再子数组内累加)但是时间复杂度很高(O(n³))

所以我们应该寻找一个时间复杂度较低的方法

第一步，我们怎么快速的算子数组的和？

我们可以巧妙利用前缀和来计算

前缀和：设arr[i]是数组中的元素，那么arr[0]+arr[1]+…+arr[i]就为arr[i]的前缀和

举个栗子：

【-3,1,2,4,0,-1,5】中，4位置的前缀和就为-3+1+2+4=4

那么我们就能得到(设sum(i,j)是i到j的区间和)

sum(i,j)=presum[j]+presum[i-1]

画图理解~

当然，我们每次要计算子区间和的时候都要算两次前缀和，为了方便，我们把每个位置的前缀和存在新数组sum中

比如，这个数组的前缀和数组是

【-3,-2,0,4,4,3,8】

第二步，拿了前缀和怎么求出合适的数组？

我们可以做以下的转化

求以每个数字为结尾的数组有多少符合要求，然后将它们相加

比如，以1为结尾的数组有0-1,1-1，设符合要求的有a个，以3为结尾的数组有0-3,1-3,2-3,3-3，设符合要求的有b个，…最后结果就是a+b+…

而我们的目标就放在了如何计算出某个数字结尾的数组是否符合要求

我们就可以进一步转化
设我们要求以j为结尾的数组的要求

如果我们的presum[i]在范围[num[j]-upper,num[j]-lower]，那么我们的sum(i,j)是符合要求的数组

为什么呢？具体例子举例

【-3,-2,0,4,4,3,8】如果我们要求的范围在[-5,5]之间

我们如果要求[0-3]这个数组是否符合要求，只需要求3的前缀和在不在[-1,9]之间

因为如果[-1,9]在区间内，那么我们加上现在的末尾数字4，它也一定在范围内

第三步：我们知道了统计原理后，怎么快速求出来答案？

我们自然要用到归并排序了

因为归并排序可以先在小区间内计算，然后再把范围扩大，达到了一个分治的效果

在归并的什么时机计算呢？

我们可以在归并的右区间中遍历，让它们每个数做为子数组的末尾，让每个区间逐个计算左区间是否在[num-upper,num-lower]中

在计算过程中，我们可以观察到一个规律

因为归并排序后，右区间是有序的，所以我们的范围区间时不递减的

所以我们可以通过滑动窗口来统计

因为符合要求的窗口区间只会向右，而不会回退

左窗口指向左区间在范围内的最小值，右指向最大

最后，看每个右区间划分的windows中区间内存在多少数，累加到答案，求出结果

class Solution {
public:
    int Merge(vector<long>&sum,int l,int m,int r,int lower,int upper)
    {
        int ans=0;
        int windowsL=l;
        int windowsR=l;
        for(int i=m+1;i<=r;i++)
        {
            long newlow=sum[i]-upper;
            long newup=sum[i]-lower;
            while(windowsL<=m&&sum[windowsL]<newlow)//
            {
                windowsL++;
            }
            while(windowsR<=m&&sum[windowsR]<=newup)//
            {
                windowsR++;
            }
            ans+=windowsR-windowsL;//这里是求窗口中有多少数字
        }
        long* help = (long*)malloc(sizeof(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 < (r - l + 1); i++) {
		sum[l + i] = help[i];
	}
	free(help);
    return ans;
    }
    int Count(vector<long>&sum,int l,int r,int lower,int upper)
    {
        if(l==r)
        {
            return sum[l] >= lower && sum[r] <= upper ? 1 : 0;
        }//这里是从0开始的数组到某个数字结尾的情况,比如0-1,0-4等（小区间内没有数字）
        int mid=l+((r-l)>>1);
        int count1=Count(sum,l,mid,lower,upper);
        int count2=Count(sum,mid+1,r,lower,upper);
        return count1+count2+Merge(sum,l,mid,r,lower,upper);//归并操作

    }
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        vector<long>sums;
        int n=nums.size();
        sums.push_back(nums[0]);
        for(int i=1;i<n;i++)
        {
            sums.push_back(sums[i-1]+nums[i]);
        }//求前缀和
        return Count(sums,0,n-1,lower,upper);
    }
};