LeetCode 327. 区间和的个数 JAVA

一时失言乱红尘 2022-12-19 11:58 105阅读 0赞

给定一个整数数组 nums，返回区间和在 \[lower, upper\] 之间的个数，包含 lower 和 upper。  
区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

示例:
    
    输入: nums = [-2,5,-1], lower = -2, upper = 2,
    输出: 3 
    解释: 3个区间分别是: [0,0], [2,2], [0,2]，它们表示的和分别为: -2, -1, 2。
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/count-of-range-sum
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

推荐一个自己觉得写得很好的题解：https://leetcode-cn.com/problems/count-of-range-sum/solution/shuo-ming-yi-xia-guan-fang-gui-bing-pai-xu-by-sing/

class Solution {
        
        public int countRangeSum(int[] nums, int lower, int upper) {
        
            long sum[]=new long[nums.length+1];
            long s=0;
            for(int i=0;i<nums.length;i++){
        
                s+=nums[i];
                sum[i+1]=s;
            }
            return countRangeSum(sum,lower,upper,0,sum.length-1);
        }
        public int countRangeSum(long[] sum, int lower, int upper,int left,int right){
        
            if(left==right) return 0;
            int mid=(right+left)/2;
            int n1=countRangeSum(sum,lower,upper,left,mid);
            int n2=countRangeSum(sum,lower,upper,mid+1,right);
            int ret=n1+n2;
            int i=left;
            int l=mid+1;
            int r=mid+1;
            while(i<=mid){
        
                while(l<=right&&sum[l]-sum[i]<lower) l++;
                while(r<=right&&sum[r]-sum[i]<=upper)r++;
                ret+=(r-l);
                i++;
            }
            //重新排序sum数组只是为了方便归并计算，并不会改变区间的点。
            int[] sorted = new int[right - left + 1];
                int p1 = left, p2 = mid + 1;
                int p = 0;
                while (p1 <= mid || p2 <= right) {
        
                    if (p1 > mid) {
        
                        sorted[p++] = (int) sum[p2++];
                    } else if (p2 > right) {
        
                        sorted[p++] = (int) sum[p1++];
                    } else {
        
                        if (sum[p1] < sum[p2]) {
        
                            sorted[p++] = (int) sum[p1++];
                        } else {
        
                            sorted[p++] = (int) sum[p2++];
                        }
                    }
                }
                for (int j = 0; j < sorted.length; j++) {
        
                    sum[left + j] = sorted[j];
                }
                return ret;
        }
    }