java solution, not a very good one, worked and beat 29%


  • 0
    D
    
    public class Solution {
        public int countRangeSum(int[] nums, int lower, int upper) {
            if(nums == null || nums.length == 0)
                return 0;
            
            int len = nums.length;
            int res = 0;
            
            long[][] sum = new long[len + 1][2];
            
            for(int i = 1; i <= len; i++){
                sum[i][0] = sum[i - 1][0] + nums[i - 1];
                sum[i][1] = i;
            }
            
            Arrays.sort(sum, new Comparator<long[]>(){
               public int compare(long[] a, long[] b){
                    if(a[0] < b[0])
                        return - 1;
                    else if(a[0] > b[0])
                        return 1;
                    else if(a[1] < b[1])
                        return -1;
                    else if(a[1] > b[1])
                        return 1;
                    else
                        return 0;
               } 
            });
            
            for(long[] entry: sum){
                long l = entry[0] + lower;
                long h = entry[0] + upper;
                
                if(l > sum[len][0] || h < sum[0][0])
                    continue;
                
                int start = search_l(sum, l);
                int end = search_h(sum, h);
                
                for(int i = start; i <= end; i++){
                    if(sum[i][1] > entry[1])
                        res++;
                }
            }
            
            return res;
        }
        
        public int search_l(long[][] sum, long num){
            int left = 0;
            int right = sum.length - 1;
            
            if(num < sum[0][0])
                return 0;
            
            while(left < right){
                int mid = left + (right - left) / 2;
                
                if(sum[mid][0] < num){
                    left = mid + 1;
                }
                else{
                    right = mid;
                }
            }
            
            return left;
        }
        
        public int search_h(long[][] sum, long num){
            int left = 0;
            int right = sum.length - 1;
            
            if(num > sum[right][0])
                return right;
            
            while(left < right - 1){
                int mid = left + (right - left) / 2;
                
                if(sum[mid][0] > num){
                    right = mid - 1;
                }
                else{
                    left = mid;
                }
            }
            
            if(sum[right][0] <= num)
                return right;
            else
                return left;
        }
        
    }
    
    
    

Log in to reply
 

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