跳转至

区间和的个数

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

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

题解

区间和可以转化为前缀和的问题。我们计算前缀和数组pre，那么只需要找到i<j使得：

lower <= pre[j]-pre[i] <= upper

暴力

我们可以直接用前缀和数组暴力求解如下：

def f(nums, lower, upper):
    pre = [0]
    for num in nums:
        pre.append(num+pre[-1])
    return sum(
        lower<=pre[j]-pre[i]<=upper 
        for j in range(len(nums)+1)
        for i in range(j)
    )

这样的算法时间复杂度是O(n^2)。

树状数组

这是经典的前缀问题，树状数组刚好是为此而生。

当然，树状数组不是拿来替代前缀和数组pre的，我们这里用它来实现高效地计数。

前面提到，本题需要在前缀数组中找到i<j使得：

lower <= pre[j]-pre[i] <= upper

也就是对于每一个j，寻找有多少个（比j小的）i，满足

pre[j]-upper <= pre[i] <= pre[j]-lower

我们用一个例子来说明这个过程：

  • nums=[-2,5,-1], lower=-2, upper=2
  • 首先求得前缀和数组为pre=[0,-2,3,2]
  • 对于0，我们需要找到-2,2之间的数值，并且只能在0的左侧寻找
    • 它的左侧显然不存在满足条件的数值，res=0
  • 对于-2，我们需要找到-4,0之间的数值
    • 它的左侧有一个数值0满足条件，res=1
  • 对于3，我们需要找到1,5之间的数值
    • 它的左侧不存在满足条件的数值，res=1
  • 对于2，我们需要找到0,4之间的数值
    • 它的左侧有0和3都满足，res=3
  • 最终我们求的所有满足条件的区间和（前缀和的差）有三个：
    • 2-0，也就是原始数组中的-2+5-1
    • 2-3，也就是原始数组中的-1
    • -2-0，也就是原始数组中的-2

如此看来，我们只需要维护一个对前缀和数组pre进行前缀计数的树状数组tree，它的含义是：

tree.query(x) = 有多少前缀和小于等于x

然后我们每次计算：

tree.query(pre[j]-lower) - tree.query(pre[j]-upper)

即可。

Info

对于每一个j，我们要寻找有多少个（比j小的）i，满足条件。

所以，我们应该从左往右更新树状数组，这样就避免了比j大的i被计数。

另外还有一个小trick。考虑到这里数组元素的值域可能很大，我们如果直接用原始数据来做索引，树状数组的大小就无法控制了。因此一般的做法是取rank，实现离散化，从而控制树状数组的大小。

具体的实现如下：

这个解题代码和最长递增子列长得差不多，树状数组的题目大概都是如此？

class FT:
    def __init__(self, n):
        self.c = [0]*(n+1)
        self.n = n
    def update(self, x, v):
        while x<=self.n:
            self.c[x] += v
            x += x&-x
    def query(self, x):
        res = 0
        while x>0:
            res += self.c[x]
            x -= x&-x
        return res

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        # 计算前缀和数组
        pre = [0]
        for num in nums:
            pre.append(num+pre[-1])
        # 把所有可能出现的数字都离散化一下
        spre = sorted(set(v for s in pre for v in (s,s-lower,s-upper)))
        # 建Fenwick树，大小是所有可能出现的数字
        n = len(spre)
        tree = FT(n)
        # 我们用二分搜索来索引数字
        from bisect import bisect_left
        res=0
        for s in pre: # 遍历的是原始前缀和数组，不是排序过的
            # 计算离散化的编号（实际上就是rank）
            ## 由于我们的spre一定包含这些数字
            ## 所以计算出来的index需要 +1 才对应于树状数组的标号
            ## 例如：bisect_left([0,1,3,8], 1) + 1 == 2
            r = bisect_left(spre, s-lower) + 1
            l = bisect_left(spre, s-upper) + 1
            x = bisect_left(spre, s) + 1
            # 我们要找的是 s 右侧的前缀和
            res += tree.query(r) - tree.query(l-1) # 第一个s=0，不需要初始化
            # 因此按照从左往右的顺序初始化即可
            tree.update(x, 1)
        return res

显然，算法时间复杂度降低为了O(nlog(n))。

排序

官方题解还有一个归并排序的解法，没太看懂，懒得看了。

归并排序倒是值得复习一下，请看Leetcode 912: 排序数组。

最后更新: 2025-08-14 22:32:20
创建日期: 2025-08-14 22:32:20

广告

人要恰饭的嘛🤑🤑

评论