給定一個整數數組 nums，返回區間和在 [lower, upper] 之間的個數，包含 lower 和 upper。
區間和 S(i, j) 表示在 nums 中，位置從 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

說明:
最直觀的算法復雜度是 O(n²) ，請在此基礎上優化你的算法。

示例:

輸入: nums = [-2,5,-1], lower = -2, upper = 2, 輸出: 3 解釋: 3個區間分別是: [0,0], [2,2], [0,2]，它們表示的和分別為: -2, -1, 2。

Python

import bisect from typing import Listclass Solution:def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:s = [0]res = cur = 0for v in nums:cur += vres += bisect.bisect_right(s, cur - lower) - bisect.bisect_left(s, cur - upper)bisect.insort_right(s, cur)return res

總結

以上是生活随笔為你收集整理的327. Count of Range Sum 区间和的个数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。