Accepted Java solution using BST and range search.


  • 0
    Z

    Use sum[i] (sum from nums[0] to nums[i]) as node key to build the BST.

    if we want ( lower <= sum[j] - sum[i] <= upper ), which is equal to ( sum[j] - upper <= sum[i] <= sum[j] - lower )
    So the problem can be viewed as counting the nodes between sum[j] - upper and sum[j] - lower form previously-built BST.

    Two recursive helper funtions:
    searchRange: search for how many nodes in the previously-built BST, that fall into the provided range;
    insert: used for building the BST, also handles duplicates.

    Average runtime should be O(nlogn).

    public class Solution {
        class TreeNode {
            long val;  // need to be long to avoid int overflow
            int rep;  // count repeated sum[i]
            TreeNode left,  right;
            TreeNode (long val) {
                this.val = val; this.rep = 1;
                left = null; right = null;
            }
        }
        
        public int countRangeSum(int[] nums, int lower, int upper) {
            int res = 0;
            long sum = 0;
            TreeNode root = new TreeNode(0L); // dummy root
            for (int i = 0; i < nums.length; i++) {
                sum += nums[i];
                res += searchRange(root, sum - upper, sum - lower);
                insert(root, sum);
            }
            return res;
        }
        
        private int searchRange(TreeNode root, long low, long high) {
            if (root == null) return 0;
            int res = 0;
            
            if (root.val > low) res += searchRange(root.left, low, high);
            if (root.val >= low && root.val <= high) res += root.rep;
            if (root.val < high) res += searchRange(root.right, low, high);
            
            return res;
        }
        
        private TreeNode insert(TreeNode root, long key) {
            if (root == null) return new TreeNode(key);
            
            if (root.val > key) root.left = insert(root.left, key);
            else if (root.val < key) root.right = insert(root.right, key);
            else root.rep++;
            
            return root;
        }
    }

Log in to reply
 

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