Given an integer array
Range sum
nums
, return the number of range sums that lie in [lower, upper]
inclusive.Range sum
S(i, j)
is defined as the sum of the elements in nums
between indices i
and j
(i
≤ j
), inclusive.
Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.
A naive algorithm of O(n2) is trivial. You MUST do better than that.
Example:
Given nums =
Return
The three ranges are :
Solution 1: Use Segment TreeGiven nums =
[-2, 5, -1]
, lower = -2
, upper = 2
,Return
3
.The three ranges are :
[0, 0]
, [2, 2]
, [0, 2]
and their respective sums are: -2, -1, 2
.Solution 2: Use Binary Search Tree
No comments:
Post a Comment