C/C++教程

LeetCode327. 区间和的个数

本文主要是介绍LeetCode327. 区间和的个数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

327. 区间和的个数

题目描述:给你一个整数数组\(nums\),求它的所有子数组中满足\(lower \leq sum(sub_{nums}) \leq upper\) 的个数。其中\(sub_{nums}\)表示数组\(nums\)的一个子数组,\(sum()\)表示对该数组中的元素求和。

思路:先考虑前缀和,那么一个子数组的和可以表示成\(preSum_{right} - preSum_{left - 1}\),我们顺序枚举,令\(x = preSum_{left - 1}\),那么就是求有个少个\(x\)满足\(lower \leq curSum - x \leq upper\)。转换一下

\[\begin{cases} x \leq up = curSum - lower\\ x \geq low = curSum - upper \end{cases} \]

那么我们只需要通过某种方式求出有多少前缀和满足\(low \leq preSum \leq up\)。因为涉及单点修改和区间查询,所以可以使用树状数组,考虑到这题数据范围很大,所以先预处理所有的\(sum\;up\;low\),然后离散化,在进行答案的求解。

时间复杂度:\(O(nlogn)\)

参考代码

class Solution {
    private int[] tree = new int[300005];
    private int lowbit(int x){return x&-x;}
    private void add(int idx , int n){
        while(idx <= n){
            tree[idx] += 1;
            idx += lowbit(idx);
        }
        return ;
    }
    private int getsum(int idx){
        int res = 0;
        while(idx > 0){
            res += tree[idx];
            idx -= lowbit(idx);
        }
        return res;
    }
    private int getres(int up , int low){
        if(up < low) return 0;
        return getsum(up) - getsum(low - 1);
    }
    public int countRangeSum(int[] nums, int lower, int upper) {
        Set<Long> set = new TreeSet<>();
        set.add(0l);
        int n = nums.length;
        Long sum = 0l;
        for(int i = 0 ; i < n ; ++i){
            sum += nums[i];
            set.add(sum);
            set.add(sum - lower);
            set.add(sum - upper);
        }
        HashMap<Long , Integer> map = new HashMap<>();
        int cur = 0;
        for(Long key : set) map.put(key , ++cur);
        sum = 0l;
        add(map.get(0l) , cur);
        int res = 0;
        for(int i = 0 ; i < n ; ++i){
            sum += nums[i];
            int up = map.get(sum - lower), low = map.get(sum - upper);
            res += getres(up , low);
            add(map.get(sum) , cur);
        }
        return res;
    }
}
这篇关于LeetCode327. 区间和的个数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!