0327：区间和的个数（★★）

2015-11-23 约 445 字预计阅读 1 分钟次阅读

力扣第 327 题

题目

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

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

示例 1：

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

示例 2：

输入：nums = [0], lower = 0, upper = 0
输出：1

提示：

1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1
-10⁵ <= lower <= upper <= 10⁵
题目数据保证答案是一个 32 位 的整数

分析

区间和容易想到前缀和，先得到前缀和数组 P
遍历 j，在 P[:j] 中找 [P[j]-upper,P[j]-lower] 范围内的个数即可
可以维护有序集合，二分即可

解答

1
2
3
4
5
6
7
8


class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        from sortedcontainers import SortedList
        res, sl = 0, SortedList()
        for x in accumulate([0]+nums):
            res += sl.bisect_right(x-lower)-sl.bisect_left(x-upper)
            sl.add(x)
        return res

833 ms

*附加

还可以用 cdq 分治，分成排好序的两部分，计算前半部分对后半部分的贡献。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        def cdq(A,l,r):
            if l==r:
                return 0
            m = (l+r)//2
            B,C = [],[]
            for i in A:
                (C if i>m else B).append(i)
            res = cdq(B,l,m)+cdq(C,m+1,r)
            j,k=0,0
            for i in C:
                while k<len(B) and P[B[k]]<=P[i]-lower:
                    k += 1
                while j<len(B) and P[B[j]]<P[i]-upper:
                    j += 1
                res += k-j
            return res
        P = [0]+list(accumulate(nums))
        n = len(P)
        A = sorted(range(n),key=lambda i:P[i])
        return cdq(A,0,n-1)

1067 ms

目录

0327：区间和的个数（★★）

题目

分析

解答

*附加