327. 区间和的个数

Hard

题目描述

给你一个整数数组 nums 以及两个整数 lower 和 upper。求数组中，值位于范围 [lower, upper]（包含 lower 和 upper）之内的 区间和的个数。

区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

示例 1：

输入：nums = [-2,5,-1], lower = -2, upper = 2
输出：3
解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。

示例 2：

输入：nums = [0], lower = 0, upper = 0
输出：1

提示：

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
-10^5 <= lower <= upper <= 10^5
题目数据保证答案是一个 32 位 的整数

解题思路

这道题要求统计所有区间和在 [lower, upper] 范围内的区间个数。直接枚举所有区间的时间复杂度是 O(n²)，对于 10^5 的数据规模会超时。

思路分析：

我们可以使用前缀和的思想。设前缀和数组为 preSum，其中 preSum[i] 表示 nums[0...i-1] 的和。那么区间 [i,j] 的和就是 preSum[j+1] - preSum[i]。

问题转化为：对于每个位置 j，统计有多少个 i ≤ j 使得 lower ≤ preSum[j+1] - preSum[i] ≤ upper，即 preSum[j+1] - upper ≤ preSum[i] ≤ preSum[j+1] - lower。

主要解法：

归并排序法（推荐）：在归并排序的过程中，当合并左右两部分时，对于右半部分的每个前缀和，在左半部分中查找满足条件的前缀和个数。由于左右部分都是有序的，可以用双指针技术高效统计。
线段树/树状数组法：将前缀和离散化后，用线段树或树状数组维护每个前缀和出现的次数，动态查询范围内的个数。
有序集合法：使用 multiset 等有序数据结构维护已处理的前缀和，利用二分查找统计范围内的个数。

归并排序法最为经典，时间复杂度 O(n log n)，空间复杂度 O(n)，是最优解法。

代码实现

class Solution {
public:
    int countRangeSum(vector<int>& nums, int lower, int upper) {
        vector<long long> preSum(nums.size() + 1, 0);
        for (int i = 0; i < nums.size(); i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        
        return mergeSort(preSum, 0, preSum.size() - 1, lower, upper);
    }
    
private:
    int mergeSort(vector<long long>& preSum, int left, int right, int lower, int upper) {
        if (left >= right) return 0;
        
        int mid = left + (right - left) / 2;
        int count = mergeSort(preSum, left, mid, lower, upper) + 
                   mergeSort(preSum, mid + 1, right, lower, upper);
        
        // 统计跨越mid的有效区间
        int i = mid + 1, j = mid + 1;
        for (int k = left; k <= mid; k++) {
            while (i <= right && preSum[i] - preSum[k] < lower) i++;
            while (j <= right && preSum[j] - preSum[k] <= upper) j++;
            count += j - i;
        }
        
        // 合并两个有序数组
        vector<long long> temp(right - left + 1);
        int p1 = left, p2 = mid + 1, p = 0;
        while (p1 <= mid && p2 <= right) {
            if (preSum[p1] <= preSum[p2]) {
                temp[p++] = preSum[p1++];
            } else {
                temp[p++] = preSum[p2++];
            }
        }
        while (p1 <= mid) temp[p++] = preSum[p1++];
        while (p2 <= right) temp[p++] = preSum[p2++];
        
        for (int i = 0; i < temp.size(); i++) {
            preSum[left + i] = temp[i];
        }
        
        return count;
    }
};

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        preSum = [0]
        for num in nums:
            preSum.append(preSum[-1] + num)
        
        def mergeSort(left, right):
            if left >= right:
                return 0
            
            mid = (left + right) // 2
            count = mergeSort(left, mid) + mergeSort(mid + 1, right)
            
            # 统计跨越mid的有效区间
            i = j = mid + 1
            for k in range(left, mid + 1):
                while i <= right and preSum[i] - preSum[k] < lower:
                    i += 1
                while j <= right and preSum[j] - preSum[k] <= upper:
                    j += 1
                count += j - i
            
            # 合并两个有序数组
            preSum[left:right+1] = sorted(preSum[left:right+1])
            
            return count
        
        return mergeSort(0, len(preSum) - 1)

public class Solution {
    public int CountRangeSum(int[] nums, int lower, int upper) {
        long[] preSum = new long[nums.Length + 1];
        for (int i = 0; i < nums.Length; i++) {
            preSum[i + 1] = preSum[i] + nums[i];
        }
        
        return MergeSort(preSum, 0, preSum.Length - 1, lower, upper);
    }
    
    private int MergeSort(long[] preSum, int left, int right, int lower, int upper) {
        if (left >= right) return 0;
        
        int mid = left + (right - left) / 2;
        int count = MergeSort(preSum, left, mid, lower, upper) + 
                   MergeSort(preSum, mid + 1, right, lower, upper);
        
        // 统计跨越mid的有效区间
        int i = mid + 1, j = mid + 1;
        for (int k = left; k <= mid; k++) {
            while (i <= right && preSum[i] - preSum[k] < lower) i++;
            while (j <= right && preSum[j] - preSum[k] <= upper) j++;
            count += j - i;
        }
        
        // 合并两个有序数组
        long[] temp = new long[right - left + 1];
        int p1 = left, p2 = mid + 1, p = 0;
        while (p1 <= mid && p2 <= right) {
            if (preSum[p1] <= preSum[p2]) {
                temp[p++] = preSum[p1++];
            } else {
                temp[p++] = preSum[p2++];
            }
        }
        while (p1 <= mid) temp[p++] = preSum[p1++];
        while (p2 <= right) temp[p++] = preSum[p2++];
        
        for (int i = 0; i < temp.Length; i++) {
            preSum[left + i] = temp[i];
        }
        
        return count;
    }
}

var countRangeSum = function(nums, lower, upper) {
    const preSum = [0];
    for (const num of nums) {
        preSum.push(preSum[preSum.length - 1] + num);
    }
    
    function mergeSort(left, right) {
        if (left >= right) return 0;
        
        const mid = Math.floor((left + right) / 2);
        let count = mergeSort(left, mid) + mergeSort(mid + 1, right);
        
        // 统计跨越mid的有效区间
        let i = mid + 1, j = mid + 1;
        for (let k = left; k <= mid; k++) {
            while (i <= right && preSum[i] - preSum[k] < lower) i++;
            while (j <= right && preSum[j] - preSum[k] <= upper) j++;
            count += j - i;
        }
        
        // 合并两个有序数组
        const temp = [];
        let p1 = left, p2 = mid + 1;
        while (p1 <= mid && p2 <= right) {
            if (preSum[p1] <= preSum[p2]) {
                temp.push(preSum[p1++]);
            } else {
                temp.push(preSum[p2++]);
            }
        }
        while (p1 <= mid) temp.push(preSum[p1++]);
        while (p2 <= right) temp.push(preSum[p2++]);
        
        for (let i = 0; i < temp.length; i++) {
            preSum[left + i] = temp[i];
        }
        
        return count;
    }
    
    return mergeSort(0, preSum.length - 1);
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

解法	时间复杂度	空间复杂度
归并排序法	O(n log n)	O(n)
线段树/树状数组法	O(n log n)	O(n)
有序集合法	O(n log n)	O(n)

其中 n 为数组长度。归并排序法是最优解，时间复杂度主要来自于分治递归的 log n 层，每层需要 O(n) 时间进行合并和统计。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目