LeetCode 327. 区间和的个数

2025-12-29 HGNULB 约 13 分钟

文章信息 6 个分类 8 个标签

分类

题目描述

✅ 327. 区间和的个数

题意分析

统计有多少个连续子数组，它们的元素和落在闭区间 [lower, upper] 内。要的是个数，不需要列出这些子数组，也不需要知道它们的位置。

「求个数而非求具体解」是一个强信号：说明可以用某种聚合式的统计手段（排序、树状数组、分治合并），不必真的枚举出每一个子数组。

子数组和天然可以写成两个前缀和之差：区间 [l, r] 的和等于 pre[r+1] - pre[l]。于是问题被改写成：在前缀和数组里，有多少对下标 (x, y) 满足 x < y 且 lower <= pre[y] - pre[x] <= upper。原来的「区间」条件变成了纯粹的「有序数对 + 差值落在范围内」，这是本题所有解法的共同起点。

数据规模上数组长度可达 10^5，元素取值覆盖整个 int 范围，lower 和 upper 也是 int。10^5 长度意味着 $O(n^2)$ 的枚举（10^10 次）必然超时，必须做到 $O(n \log n)$。而元素可正可负且长度 10^5，前缀和最大能达到约 10^5 × 2^31，远超 int 范围，必须全程用 64 位。

元素可为负这一点还有个后果：前缀和数组不单调，所以不能用滑动窗口那套「右端点右移则和单调增」的推理。

边界包括：数组只有一个元素；lower == upper；所有元素为 0 而区间包含 0（此时答案是所有子数组数量）。

解法：前缀和 + 归并排序

核心思路

暴力做法是枚举所有 (x, y) 对，检查 pre[y] - pre[x] 是否落在范围内，$O(n^2)$。瓶颈在于对每个 y，我们都把左边所有 x 重扫一遍，而这些 x 之间没有任何组织，无法批量判断。

把条件变形：lower <= pre[y] - pre[x] <= upper 等价于 pre[x] >= pre[y] - upper 且 pre[x] <= pre[y] - lower，也就是「pre[x] 落在区间 [pre[y] - upper, pre[y] - lower] 内」。所以每个 y 需要的是「左侧有多少个前缀和落在某个值区间里」——一个典型的范围计数查询。只要左侧那批数是有序的，这个计数就能用两次二分或双指针得到。

归并排序恰好在合并阶段免费提供了这个条件：递归返回时左半段和右半段各自已经有序，而它们在原数组中的下标关系又天然满足「左半的下标全部小于右半的下标」。于是「x < y」这个约束被分治结构自动保证，剩下的只是在两段有序数组之间做范围计数。

由此定义分治的语义：mergeCount(pre, left, right) 返回「下标对 (x, y) 同时落在 [left, right) 内且满足条件的数量」，副作用是把 pre[left..right) 就地排成升序。

不变量有两条。第一条：递归返回时，pre[left..right) 已升序排列，但其中元素的集合与调用前完全相同（只是重排）。第二条：任意一对满足条件的 (x, y) 恰好被统计一次——要么两者同属左半（在左侧递归里统计），要么同属右半（在右侧递归里统计），要么跨越中点（在本层的跨区间统计里处理），三种情况互斥且穷尽。

跨区间统计用双指针：外层遍历左半的每个 pre[l]，用 i 找出右半中第一个使 pre[i] - pre[l] >= lower 的位置，用 j 找出第一个使 pre[j] - pre[l] > upper 的位置，则 [i, j) 内的元素都合法，贡献 j - i。两个指针都只会单向前进，因为左半已升序，pre[l] 递增会让两个阈值 pre[l] + lower 和 pre[l] + upper 同步递增，右半中的分界点只会往右移，绝不回退。这正是把本层的跨区间统计压到 $O(n)$ 的关键。

顺序上还有一个必须点明的细节：跨区间统计必须在归并之前完成。归并会把两段混在一起，一旦混合，「哪些元素来自左半、哪些来自右半」的信息就丢了，双指针的前提也就不成立。

解题步骤

先构造长度为 n+1 的前缀和数组，pre[0] = 0 表示空前缀。之所以要留空前缀，是因为以下标 0 开头的子数组需要 pre[0] 作为减数，缺了它会漏掉所有前缀型子数组。

前缀和数组用 64 位类型。之所以必须如此，是因为 10^5 个绝对值接近 2^31 的元素累加会溢出 32 位，溢出后的差值判断完全失真。

对整个 pre 数组调用分治函数，区间用左闭右开表示。之所以选左闭右开，是因为它让 mid 天然成为两段的分界点，左半是 [left, mid)、右半是 [mid, right)，不需要在下标上做加一减一的调整。

递归出口是区间长度不超过 1 时返回 0。之所以是「不超过 1」而不是「等于 0」，是因为单个元素既构不成数对，本身也已经是有序的，无需处理。

先递归左右两半并把返回值累加。之所以要先递归，是因为跨区间统计依赖「两半各自有序」，而这个性质正是子递归的副作用。

跨区间统计时，i 和 j 都从 mid 开始，且在整个外层循环中不重置。之所以不能在每个 l 处重新从 mid 开始扫，是因为那样本层代价会退化到 $O(n^2)$，总复杂度变成 $O(n^2 \log n)$，比暴力还慢；单调性保证了不重置的正确性。

i 的推进条件用严格小于 lower，j 的推进条件用小于等于 upper。之所以两个不对称，是因为区间是闭的：i 要停在第一个「够大」的位置（该位置本身合法），j 要停在第一个「太大」的位置（该位置本身不合法），于是合法元素恰好是 [i, j)，数量为 j - i。

统计完成后做标准归并，把两段合并成有序并写回原数组。之所以要写回而不是只在临时数组里排好，是因为上一层递归会把本区间当作「已排好序的一半」直接使用。

返回三部分之和：左半内部、右半内部、跨区间。

以 nums = [-2, 5, -1]、lower = -2、upper = 2 走一遍，预期答案是 3（子数组 [0,0] 和为 -2、[2,2] 和为 -1、[0,2] 和为 2）。

前缀和 pre = [0, -2, 3, 2]，长度 4，对 [0, 4) 调用。

第一层 mid = 2。左侧递归处理 [0, 2) 即 [0, -2]：其 mid = 1，两个子区间长度都为 1 返回 0；跨区间统计中 l = 0（值 0），右半是 [-2]，i 从 1 开始，pre[1] - pre[0] = -2，不小于 lower = -2，i 停在 1；j 检查 -2 <= 2 成立，j 前进到 2 越界停下；贡献 2 - 1 = 1。这一对对应子数组 [0,0]，和为 -2，正确。归并后 pre[0..2) = [-2, 0]，返回 1。

右侧递归处理 [2, 4) 即 [3, 2]：mid = 3，两子区间返回 0；跨区间中 l = 2（值 3），右半是 [2]，i 从 3 开始，pre[3] - pre[2] = 2 - 3 = -1，不小于 -2，i 停在 3；j 检查 -1 <= 2 成立，j 前进到 4 越界；贡献 4 - 3 = 1。这一对对应子数组 [2,2]，和为 -1，正确。归并后 pre[2..4) = [2, 3]，返回 1。

回到第一层做跨区间统计，此时左半是 [-2, 0]、右半是 [2, 3]。i = j = 2。l = 0（值 -2）：i 检查 pre[2] - (-2) = 4，不小于 -2，i 停在 2；j 检查 4 <= 2 不成立，j 停在 2；贡献 0。l = 1（值 0）：i 检查 pre[2] - 0 = 2，不小于 -2，i 仍为 2；j 检查 2 <= 2 成立，j 前进到 3；再检查 pre[3] - 0 = 3 <= 2 不成立，j 停在 3；贡献 3 - 2 = 1。这一对是 pre[3] - pre[1]（排序前的原始含义即 2 - 0），对应子数组 [0,2]，和为 2，正确。

总计 1 + 1 + 1 = 3，与预期一致。

代码实现

class Solution {
    public int countRangeSum(int[] nums, int lower, int upper) {
        long[] pre = new long[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            pre[i + 1] = pre[i] + nums[i];
        }
        return mergeCount(pre, 0, pre.length, lower, upper);
    }

    private int mergeCount(long[] pre, int left, int right, int lower, int upper) {
        if (right - left <= 1) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        int count = mergeCount(pre, left, mid, lower, upper)
                + mergeCount(pre, mid, right, lower, upper);

        int i = mid;
        int j = mid;
        for (int l = left; l < mid; l++) {
            while (i < right && pre[i] - pre[l] < lower) {
                i++;
            }
            while (j < right && pre[j] - pre[l] <= upper) {
                j++;
            }
            count += j - i;
        }

        long[] merged = new long[right - left];
        int p1 = left;
        int p2 = mid;
        int p = 0;
        while (p1 < mid && p2 < right) {
            if (pre[p1] <= pre[p2]) {
                merged[p++] = pre[p1++];
            } else {
                merged[p++] = pre[p2++];
            }
        }
        while (p1 < mid) {
            merged[p++] = pre[p1++];
        }
        while (p2 < right) {
            merged[p++] = pre[p2++];
        }
        System.arraycopy(merged, 0, pre, left, merged.length);

        return count;
    }
}

func countRangeSum(nums []int, lower int, upper int) int {
    pre := make([]int64, len(nums)+1)
    for i := 0; i < len(nums); i++ {
        pre[i+1] = pre[i] + int64(nums[i])
    }
    return mergeCount(pre, 0, len(pre), int64(lower), int64(upper))
}

func mergeCount(pre []int64, left int, right int, lower int64, upper int64) int {
    if right-left <= 1 {
        return 0
    }

    mid := left + (right-left)/2
    count := mergeCount(pre, left, mid, lower, upper) + mergeCount(pre, mid, right, lower, upper)

    i, j := mid, mid
    for l := left; l < mid; l++ {
        for i < right && pre[i]-pre[l] < lower {
            i++
        }
        for j < right && pre[j]-pre[l] <= upper {
            j++
        }
        count += j - i
    }

    merged := make([]int64, right-left)
    p1, p2, p := left, mid, 0
    for p1 < mid && p2 < right {
        if pre[p1] <= pre[p2] {
            merged[p] = pre[p1]
            p1++
        } else {
            merged[p] = pre[p2]
            p2++
        }
        p++
    }
    for p1 < mid {
        merged[p] = pre[p1]
        p1++
        p++
    }
    for p2 < right {
        merged[p] = pre[p2]
        p2++
        p++
    }
    copy(pre[left:right], merged)

    return count
}

复杂度分析

时间复杂度：$O(n \log n)$，凭据是分治把长度为 n+1 的数组递归划分出 $O(\log n)$ 层，每层的总工作量是线性的——跨区间统计里两个指针在各自区间内只单向前进不回退，归并本身也是一次线性扫描，因此每层 $O(n)$，总计 $O(n \log n)$。

空间复杂度：$O(n)$，凭据是前缀和数组占 $O(n)$，每层归并新建的临时数组在返回后即可回收、同一时刻最多存在 $O(n)$ 大小，递归栈深度是 $O(\log n)$，三者相加仍是 $O(n)$。

关键点总结

「子数组和落在某范围」这类条件应当立刻改写成「两个前缀和之差落在范围内」，把区间问题降级成数对问题；这是所有子数组求和类题目的统一入口。

数对统计中的「下标先后」约束，可以交给分治结构免费保证：左半的下标必然小于右半，于是本层只需处理跨越中点的那部分，无需再做任何下标比较。

归并排序的合并阶段是一个「免费的有序性提供者」，凡是需要「左侧有序才能快速计数」的问题（逆序对、翻转对、区间和个数）都能套进同一个框架，区别只在跨区间统计那几行。

双指针跨过整个外层循环不重置，是把本层代价压到线性的唯一办法；它的正确性来自左半有序导致阈值单调递增。写完后应该主动检查「指针有没有被误重置」。

闭区间的两端要用不对称的推进条件（下界用严格小于、上界用小于等于），这样合法元素恰好构成左闭右开的一段，个数直接是两指针之差，不需要额外加一减一。

前缀和必须用 64 位，且这是正确性问题不是防御问题：10^5 个 int 累加必然可能溢出。

面试视角：面试官会先确认你能否把子数组和转成前缀和差，再看你选归并、树状数组还是有序集合。归并是最不依赖模板记忆的答案，讲清「三类数对互斥穷尽」和「双指针不重置」两点即可；若被追问其他做法，可以提「离散化后用树状数组按 pre[y] 顺序查询区间计数」，复杂度同为 $O(n \log n)$。

易错点总结

前缀和用 int 存：用例 10^5 个值为 2×10^9 量级的元素（或反复的 Integer.MAX_VALUE），累加溢出成负数，所有差值判断失真，答案完全错误。

前缀和数组长度只开 n 而不留空前缀：用例 nums = [-2], lower = -2, upper = 2，没有 pre[0] = 0 作减数，子数组 [0,0] 无法被表示，返回 0 而非 1。

双指针 i、j 在每个 l 处重置回 mid：用例长度 10^5 的数组，本层代价从 $O(n)$ 退化成 $O(n^2)$，总复杂度变成 $O(n^2 \log n)$，比暴力还慢，直接超时。

j 的推进条件写成 pre[j] - pre[l] < upper：用例 nums = [0], lower = 0, upper = 0，pre = [0, 0]，j 不会跨过差值恰好为 0 的位置，返回 0 而非 1，闭区间上界被当成开区间。

i 的推进条件写成 pre[i] - pre[l] <= lower：用例 nums = [-2], lower = -2, upper = 2，i 越过了差值恰好等于 lower 的位置，贡献少算 1，返回 0 而非 1。

先归并再做跨区间统计：用例 nums = [-2, 5, -1]，归并后两段已混合，i、j 扫到的元素可能来自左半，统计出的数对不满足 x < y，答案偏大。

归并后忘记写回原数组：用例任意长度大于 2 的输入，上层递归拿到的两半并非有序，双指针的单调性前提破产，结果随机偏小。

递归出口写成 right - left <= 0：用例任意输入，长度为 1 的区间会继续递归，mid 等于 left，左半区间长度为 0 而右半仍为 1，无限递归导致栈溢出。

lower、upper 在 Java 里保持 int 而与 long 型的 pre 差值比较时，先把差值截断成 int 再比较：用例前缀和差值超过 int 范围的输入，截断后的值与真实差值符号都可能相反，计数错误；正确做法是让差值保持 64 位，lower/upper 自动提升。

用 count 的类型为 int 却在答案接近上限时溢出：用例长度 10^5 的全零数组配 lower = upper = 0，答案是约 5×10^9 对，超出 int；本题官方数据保证结果在 int 内，但若自行构造测试需注意这一点。

归并时比较写成 pre[p1] < pre[p2]：用例含重复前缀和的输入，本题只影响相等元素的相对顺序而不影响计数，但在需要稳定性的同框架题目（如求逆序对下标）里会直接算错。

相似题目

题目	难度	考察点
315. 计算右侧小于当前元素的个数	困难	要求返回每个位置的答案而非总数，归并时必须携带原始下标
493. 翻转对	困难	判据是 `a > 2b` 的单侧不等式，跨区间只需一个指针而非两个
剑指 Offer 51. 数组中的逆序对	困难	判据退化成简单大小比较，计数可以直接并入归并循环内部
560. 和为 K 的子数组	中等	目标是单个精确值而非区间，哈希表计数即可，无需排序
307. 区域和检索 - 数组可修改	中等	同样围绕前缀和，但要支持单点更新，考察树状数组或线段树的实现