problem327

README

< Previous 　　　　　　　　　　　　　　　　 Next >

327. Count of Range Sum (Hard)

Given an integer array nums and two integers lower and upper, 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 inclusive, where i <= j.

 

Example 1:

Input: nums = [-2,5,-1], lower = -2, upper = 2
Output: 3
Explanation: The three ranges are: [0,0], [2,2], and [0,2] and their respective sums are: -2, -1, 2.

Example 2:

Input: nums = [0], lower = 0, upper = 0
Output: 1

 

Constraints:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1
• -3 * 104 <= lower <= upper <= 3 * 104

 

Follow up: A naive algorithm of O(n2) is trivial, Could you do better than that?

Related Topics

[Sort] [Binary Indexed Tree] [Segment Tree] [Binary Search] [Divide and Conquer]

Similar Questions

1. Count of Smaller Numbers After Self (Hard)
2. Reverse Pairs (Hard)