Given an integer arraynums, return the number of range sums that lie in[lower, upper]inclusive.
Range sumS(i, j)is defined as the sum of the elements innumsbetween indicesiandj(i≤j), inclusive.

Note:
A naive algorithm ofO(n2) is trivial. You MUST do better than that.

Example:

Input: 
nums
 = 
[-2,5,-1]
, 
lower
 = 
-2
, 
upper
 = 
2
,

Output: 
3 

Explanation: 
The three ranges are : 
[0,0]
, 
[2,2]
, 
[0,2]
 and their respective sums are: 
-2, -1, 2
.

class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        if (nums == null) return 0;
        TreeMap<Long, Long> hash = new TreeMap<>();
        hash.put((long)0, (long)1);

        long sum = 0;
        int ans = 0;
        for (int num : nums){
            sum += num;
            Map<Long, Long> subMap = hash.subMap(sum - upper, true, sum - lower, true);
            for (Long val : subMap.values()){
                ans += val;
            }
            hash.put(sum, hash.getOrDefault(sum, (long)0) + 1);
        }

        return ans;
    }
}