Java TreeMap Solution


  • 1
    J

    Use method similar to LC363, but use TreeMap because there might be cases that there can be duplicate areas, we need to count all of them.

    // TreeMap solution
    public int countRangeSum(int[] nums, int lower, int upper) {
        if (lower > upper) {return 0;}
        int len = nums.length;
        
        int result = 0;
        long area = 0;
        TreeMap<Long, Integer> map = new TreeMap<>();
        map.put(area, 1);
        for (int i = 0; i < len; i++) {
            area += nums[i];
            Long ceiling = map.ceilingKey(area - upper);
            Long floor = map.floorKey(area - lower);
            if (ceiling != null && floor != null && ceiling <= floor) {
                for (Map.Entry<Long, Integer> entry : map.subMap(ceiling, true, floor, true).entrySet()) {
                    result += entry.getValue();
                }
            }
            
            if (map.containsKey(area)) {
                map.put(area, map.get(area) + 1);
            } else {
                map.put(area, 1);
            }
        }
        
        return result;
    }

Log in to reply
 

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