# LeetCode 327. Count of Range Sum

## Description

https://leetcode.com/problems/count-of-range-sum/

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 <= 105`
• `-231 <= nums[i] <= 231 - 1`
• `-105 <= lower <= upper <= 105`
• The answer is guaranteed to fit in a 32-bit integer.

## Explanation

Create a map where the value is the count of prefix sum equals to key. If there is a number in [lower, upper] equals the sum of nums[i, j], then prefix[i – 1] – number must be in the map.

## Python Solution

``````class Solution:
def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
count_sum = {0:1}

pre_sum = 0
count = 0

for num in nums:
pre_sum += num

for d in range(lower, upper + 1):
if pre_sum - d in count_sum:
count += count_sum[pre_sum - d]

count_sum[pre_sum] = count_sum.get(pre_sum, 0) + 1

return count
``````
• Time Complexity: O(N^2).
• Space Complexity: O(N).