区间和的个数
327. 区间和的个数 (Hard)
给定一个整数数组 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。
相关话题
[排序] [树状数组] [线段树] [二分查找] [分治算法]
相似题目
- 计算右侧小于当前元素的个数 (Hard)
- 翻转对 (Hard)