Accepted TreeMap solution


  • 0
    T

    For each cumulative sum[i], we need to find all the previous cumulative sum[j]'s such that sum[i]-upper<=sum[j]<=sum[i]-lower. TreeMap's subMap method can achieve this.

    public class Solution {
        public int countRangeSum(int[] nums, int lower, int upper) {
            TreeMap<Long, Integer> treeMap = new TreeMap<Long, Integer>();
            int result = 0;
            long sum=0;
            treeMap.put(sum,1);
            for(int n : nums) {
                sum+=n;
                Map<Long, Integer> map = treeMap.subMap(sum-upper,true,sum-lower,true);
                for(int i : map.values()) result+=i;
                if(!treeMap.containsKey(sum)) treeMap.put(sum,0);
                treeMap.put(sum, treeMap.get(sum)+1);
            }
            return result;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.