原题链接在这里:https://leetcode.com/problems/count-of-range-sum/
题目:
Given an integer array nums
, return the number of range sums that lie in [lower, upper]
inclusive.
Range sum S(i, j)
is defined as the sum of the elements in nums
between indices i
and j
(i
≤ j
), inclusive.
Note:
A naive algorithm of O(n2) is trivial. You MUST do better than that.
Example:
Given nums = [-2, 5, -1]
, lower = -2
, upper = 2
,
Return 3
.
The three ranges are : [0, 0]
, [2, 2]
, [0, 2]
and their respective sums are: -2, -1, 2
.
题解:
题目的意思是说给了一个int array, 计算有多少subarray的sum在[lower, upper]区间内. 给的例子是index.
建立BST,每个TreeNode的val是prefix sum. 为了避免重复的TreeNode.val, 设置一个count记录多少个重复TreeNode.val, 维护leftSize, 记录比该节点value小的节点个数,rightSize同理.
由于RangeSum S(i,j)在[lower,upper]之间的条件是lower<=sums[j+1]-sums[i]<=upper. 所以我们每次insert一个新的PrefixSum sums[k]进这个BST之前,先寻找一下rangeSize该BST内已经有多少个PrefixSum, 叫它sums[t]吧, 满足lower<=sums[k]-sums[t]<=upper, 即寻找有多少个sums[t]满足:
sums[k]-upper<=sums[t]<=sums[k]-lower
BST提供了countSmaller和countLarger的功能,计算比sums[k]-upper小的RangeSum数目和比sums[k]-lower大的数目,再从总数里面减去,就是所求
Time Complexity: O(nlogn). Space: O(n).
AC Java:
public class Solution {
public int countRangeSum(int[] nums, int lower, int upper) {
if(nums == null || nums.length == 0){
return 0;
}
int res = 0;
long [] sum = new long[nums.length+1];
for(int i = 1; i<sum.length; i++){
sum[i] = sum[i-1] + nums[i-1];
} TreeNode root = new TreeNode(sum[0]);
for(int i = 1; i<sum.length; i++){
res += rangeSize(root, sum[i]-upper, sum[i]-lower);
insert(root, sum[i]);
}
return res;
} private TreeNode insert(TreeNode root, long val){
if(root == null){
return new TreeNode(val);
}
if(root.val == val){
root.count++;
}else if(root.val > val){
root.leftSize++;
root.left = insert(root.left, val);
}else if(root.val < val){
root.rightSize++;
root.right = insert(root.right, val);
}
return root;
} private int countSmaller(TreeNode root, long val){
if(root == null){
return 0;
}
if(root.val == val){
return root.leftSize;
}else if(root.val > val){
return countSmaller(root.left, val);
}else{
return root.leftSize + root.count + countSmaller(root.right, val);
}
} private int countLarget(TreeNode root, long val){
if(root == null){
return 0;
}
if(root.val == val){
return root.rightSize;
}else if(root.val > val){
return countLarget(root.left, val) + root.count + root.rightSize;
}else{
return countLarget(root.right, val);
}
} private int rangeSize(TreeNode root, long lower, long upper){
int total = root.leftSize + root.count + root.rightSize;
int smaller = countSmaller(root, lower);
int larger = countLarget(root, upper);
return total - smaller - larger;
}
} class TreeNode{
long val;
int count;
int leftSize;
int rightSize;
TreeNode left;
TreeNode right;
public TreeNode(long val){
this.val = val;
this.count = 1;
this.leftSize = 0;
this.rightSize = 0;
}
}