My Java solution using TreeMap


  • -4
    W
    public int countRangeSum(int[] nums, int lower, int upper) {
        if(upper < lower) return 0;
        if(nums.length==0) return 0;
        int cnt=0;
        TreeMap<Long,Integer> tm=new TreeMap<Long, Integer>();
        long sum=0;
        for(int i=0;i<nums.length;i++) {
            sum+=nums[i];
            if(sum>=lower && sum<=upper) cnt++;
            long min=sum-upper;
            long max=sum-lower;
            Map<Long,Integer> submap=tm.subMap(min,max+1);
            long total=0;
            for(long val:submap.values()) total+=val;
            cnt+=total;
            if(tm.containsKey(sum)) 
                tm.put(sum,tm.get(sum)+1);
            else
                tm.put(sum,1);
        }
        
        return cnt;
    }

Log in to reply
 

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