leetcode.327. 区间和的个数——前缀和

素颜马尾好姑娘i 2022-12-19 11:45 107阅读 0赞

### 文章目录 ###

*  327. 区间和的个数
 *  代码
 *   *  暴力解法
     *  二维DP
     *  前缀和

# 327. 区间和的个数 #

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

**说明:**  
最直观的算法复杂度是  O ( n 2 ) O(n^\{2\}) O(n2) ，请在此基础上优化你的算法。

**示例:**

输入: nums = [-2,5,-1], lower = -2, upper = 2,
    输出: 3 
    解释: 3个区间分别是: [0,0], [2,2], [0,2]，它们表示的和分别为: -2, -1, 2。

# 代码 #

## 暴力解法 ##

用暴力解法，`2` 层循环，遍历所有子区间，求和并判断是否位于 `[lower,upper]` 之间，时间复杂度 `O(n^2)`。

package count_of_range_sum;
    
    /** * 327. Count of Range Sum * 327. 区间和的个数 * 题目意思是有多少个连续的区间，里面的数字总和在范围内 * */
    public class Solution { 
    	
        public int countRangeSum(int[] nums, int lower, int upper) { 
            int count = 0;
            for (int i = 0; i < nums.length; i++) { 
                long sum = 0;
                for (int j = i; j < nums.length; j++) { 
                    sum += nums[j];
                    //System.out.println(lower+" <= "+sum+" && "+sum+" <= "+upper);
                    if (lower <= sum && sum <= upper) { 
                        count++;
                    }
                }
            }
            return count;
        }
        
        public static void main(String[] args) { 
    		int[] nums = { -2,5,-1};
    		int lower = -2,upper = 2;
    		System.out.println(new Solution().countRangeSum(nums, lower, upper));
    	}
    }

## 二维DP ##

![在这里插入图片描述][2020112815182688.png]

class Solution { 
        public int countRangeSum(int[] nums, int lower, int upper) { 
            int len = nums.length;
            int ans = 0;
            // 长整型 是为了避免 整型相加 溢出
            long[][] dp = new long[len][len];
            for (int row = 0; row < len; row++) { 
                for (int col = row; col < len; col++) { 
                    if (col == row) { 
                        dp[row][col] = nums[row];
                    } else { 
                        dp[row][col] = dp[row][col - 1] + nums[col];
                    }
                    if (dp[row][col] >= lower && dp[row][col] <= upper) ans++;
                }
            }
            return ans;
        }
    }
    
    //作者：smitish

但是二维DP超时了。

## 前缀和 ##

public int countRangeSum(int[] nums, int lower, int upper) { 
        //前驱和数组+归并排序 Nlog(N)
        long[] preSum=new long[nums.length+1];  //nums[i]=preSum[i+1]-preSum[i] 所以前驱和长度多1
        long sum=0;
        for(int i=0;i<nums.length;i++){ 
            sum+=nums[i];
            preSum[i+1]=sum;
        }
        return mergesort(preSum,0,preSum.length-1,lower,upper);
    }
    
    public int mergesort(long[] arr,int left,int right,int lower,int upper){ 
        //归并分而治之，拆分待排序数据，递归实现
        if(left==right)return 0;
        int mid=(left+right)/2;
        int resLeft=mergesort(arr,left,mid,lower,upper);
        int resRight=mergesort(arr,mid+1,right,lower,upper);
        int res=resLeft+resRight;
    
        //统计当前待合并数组间的区间和个数，每一个右边元素减去每一个左边元素（表示一段区间和)
        //转化为两升序数组之间的差在某一区间的问题，维护i指向arr1，l和r指向arr2
        //让l和r分别指向与i的差在区间边界的情况，再统计个数即可,主要是为了降低时间复杂度！
        //[l,r)都符合条件
        int i=left;
        int l=mid+1;
        int r=mid+1;
        while(i<=mid){ 
            while(l<=right&&arr[l]-arr[i]<lower){ l++;}
            while(r<=right&&arr[r]-arr[i]<=upper){ r++;}
            res+=r-l;
            i++;
        }
    
        //归并，使用传统方法，维护i和j两个变量即可
        long[] temp=new long[right-left+1];
        int t=0;
        i=left;
        int j=mid+1;
        while(i<=mid&&j<=right){ 
            if(arr[i]<=arr[j])temp[t++]=arr[i++];
            else temp[t++]=arr[j++];
        }
        while(i<=mid){ temp[t++]=arr[i++];}
        while(j<=right){ temp[t++]=arr[j++];}
        t=0;
        while(t<temp.length){ arr[left++]=temp[t++];}
    
        return res;  //返回当前节点满足条件的区间和个数
    }
    
    //作者：sunflower-zzn

[2020112815182688.png]: /images/20221120/f2a2a002c4a048f6af73ab1a570103c4.png