Very Simply TreeSet Solution


  • 0
    I
    public class Solution {
        public int countRangeSum(int[] nums, int lower, int upper) {
            final TreeSet<long[]> paper = new TreeSet<>(
                (a, b) -> a[0] == b[0] ? Long.compare(a[1], b[1]) : Long.compare(a[0], b[0]));
            paper.add(new long[]{0, -1});
            
            /*
                sj - si <= upper ==> si >= sj - upper
                sj - si >= lower ==> si <= sj - lower
            */
            
            int ans = 0;
            long sum = 0;
            for(int i=0; i<nums.length; i++) {
                sum += nums[i];
                ans += paper.subSet(new long[]{sum - upper, -1}, true, new long[]{sum - lower, nums.length}, true).size();
                paper.add(new long[]{sum, i});
            }
    
            return ans;
        }
    }
    

Log in to reply
 

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