Simple Java Binary Search Solution


  • 0

    Use the conception of sum array to calculate the range sum. iterate over the sum array, for each index i using binary search to find the previous sum that is between [sum[i]-upper, sum[i]-lower]. I use a ArrayList to store all the previous sum and implemented the search1 and search2 function to find the two edge sum index.

    public class Solution {
        public int countRangeSum(int[] nums, int lower, int upper) {
            if(nums==null||nums.length==0) return 0;
            int res=0;
            List<Long> list=new ArrayList<>();
            list.add((long)0);
            long sum=0;
            for(int i=1;i<=nums.length;i++){
                sum=sum+nums[i-1];
                int lowerindex=search1(list,sum-lower);
                int upperindex=search2(list,sum-upper);
                res+=Math.max(0,lowerindex-upperindex+1);
                int insertindex=Collections.binarySearch(list, sum);
                if(insertindex<0) insertindex=-(insertindex+1);
                list.add(insertindex,sum);
            }
            return res;
        }
        
        public int search1(List<Long> list, long target){
            int l=0, r=list.size()-1;
            while(l<r){
                int mid=l+(r-l)/2;
                if(list.get(mid)>target) r=mid-1;
                else l=mid+1;
            }
            if(list.get(l)<=target) return l;
            else return l-1;
        }
        
        public int search2(List<Long> list, long target){
            int l=0, r=list.size()-1;
            while(l<r){
                int mid=l+(r-l)/2;
                if(list.get(mid)<target) l=mid+1;
                else r=mid-1;
            }
            if(list.get(l)>=target) return l;
            else return l+1;
        } 
    }
    

Log in to reply
 

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