跳转至

327. 区间和的个数#

问题描述#

给定一个整数数组 nums，返回区间和在 [lower, upper] 之间的个数，包含 lower 和 upper。
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

说明:
最直观的算法复杂度是 O(n2) ，请在此基础上优化你的算法。

示例:

输入: nums = [-2,5,-1], lower = -2, upper = 2,
输出: 3 
解释: 3个区间分别是: [0,0], [2,2], [0,2]，它们表示的和分别为: -2, -1, 2。

解题思路#

常规做法就是先计算累计和，然后遍历计算满足条件的区间。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        culsum = [0]
        t = 0
        ans = 0
        for x in nums:
            t += x
            for y in culsum:
                if lower <= t - y <= upper: # 区间 [i, j]
                    ans += 1
            culsum.append(t)
        return ans

s1.png

运行接近超时，说明 \(\mathcal{O}(n^2)\) 的复杂度还有优化的空间。

在上面的方法中，在 cumsum_list 中找到 cumsum_list[i] 满足 lower<=cumsum-cumsum_list[i]<=upper，即 cumsum-upper<=cumsum_list[i]<=cumsum-lower。

如果 cumsum_list 是有序的，就不用像上述方法一样进行遍历，只需使用二分搜索即可。所以每次我们在计算完当前位置后，将 cumsum 有序插入到 cumsum_list 中即可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
from bisect import bisect_left, bisect_right, insort
from typing import List


class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        cumsum_list = [0]
        cumsum = 0
        ans = 0
        for x in nums:
            cumsum += x
            left = bisect_left(cumsum_list, cumsum - upper)
            right = bisect_right(cumsum_list, cumsum - lower)
            ans += right - left
            insort(cumsum_list, cumsum)
        return ans

s2.png

返回顶部

在手机上阅读