LeetCode 303. 区域和检索 - 数组不可变

约 4 分钟
文章信息 8 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 5-10 字节跳动 微软 美团
标签
数组 设计 前缀和
目录

题目描述

✅ 303. 区域和检索 - 数组不可变

题意分析

要设计一个类：构造时接收一个整数数组，之后反复调用 sumRange(left, right) 返回闭区间 [left, right] 内所有元素之和。

这是一道设计题，所以要看的不是「一次查询多快」，而是构造与查询的代价怎么分摊。题面里写明了 sumRange 最多会被调用 $3 \times 10^4$ 次、数组长度也在 $10^4$ 量级，两者相乘是 $3 \times 10^8$——这正是在告诉你「每次查询现场累加」会超时，必须把公共计算搬到构造函数里做一次。

类名和题目标题里的「不可变」三个字是最强的信号：数组在构造之后不会被修改。这意味着预处理结果一旦算好就永久有效，不需要考虑更新时如何维护，也就不必上树状数组或线段树这类支持单点修改的结构。可修改的版本是另一道题（307），两者的分水岭就在这里。

区间是闭区间，两端都要计入。这一点看似琐碎，却决定了下标偏移里那个 +1 写在哪里，是本题唯一真正需要小心的地方。

边界要盯住：left 与 right 可以相等，此时区间只含一个元素；left 可以是 0，区间从数组开头起算；right 可以是最后一个下标；元素可以是负数，所以不能用任何「和非负」的假设去剪枝。

解法：前缀和

核心思路

数组不会更新，却会被反复查询区间和。若每次从 left 累加到 right，单次查询为 $O(n)$；更合适的做法是在构造对象时预处理前缀和，把重复计算提前完成。

定义 prefix[i] 为前 i 个元素之和，令 prefix[0] = 0。闭区间 [left, right] 的和就是：

\[prefix[right+1] - prefix[left]\]

两个前缀都包含 left 之前的部分，相减后只剩查询区间。

不变量：构造完成后，对任意 i，prefix[i] 都严格表示 nums[0...i-1] 的和。多保留的 prefix[0] 让从下标 0 开始的查询也无需特判。

解题步骤

  1. 创建长度为 nums.length + 1 的前缀和数组。
  2. 对每个下标 i，计算 prefix[i+1] = prefix[i] + nums[i]。
  3. 查询 [left, right] 时返回 prefix[right+1] - prefix[left]。

例如 nums = [-2,0,3,-5,2,-1]，查询 [2,5] 时计算 prefix[6] - prefix[2] = -3 - (-2) = -1。

代码实现

class NumArray {
    private final int[] prefix;

    public NumArray(int[] nums) {
        prefix = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
    }

    public int sumRange(int left, int right) {
        return prefix[right + 1] - prefix[left];
    }
}

type NumArray struct {
    prefix []int
}

func Constructor(nums []int) NumArray {
    prefix := make([]int, len(nums)+1)
    for i, value := range nums {
        prefix[i+1] = prefix[i] + value
    }
    return NumArray{prefix: prefix}
}

func (this *NumArray) SumRange(left int, right int) int {
    return this.prefix[right+1] - this.prefix[left]
}

复杂度分析

  • 构造时间复杂度：$O(n)$。
  • 查询时间复杂度：$O(1)$。
  • 空间复杂度：$O(n)$，用于保存前缀和数组。

关键点总结

  • 不可变数组加多次区间查询，是前缀和的直接使用场景。
  • prefix[i] 表示前 i 个元素，而不是以下标 i 结尾的前缀。
  • 长度取 n + 1 可以用同一公式覆盖 left = 0。
  • 闭区间右端点在前缀数组中对应 right + 1。

易错点总结

  • 返回 prefix[right] - prefix[left]：会漏掉右端点，并产生整体错位。
  • 返回 prefix[right+1] - prefix[left+1]：会漏掉左端点。
  • 只开长度 n 的数组：无法自然表示空前缀，也容易在 right = n-1 时越界。
  • 每次查询重新累加：结果正确，但没有利用数组不可变，单次查询仍是 $O(n)$。
  • 把问题当作动态数组维护：题目没有更新操作，无须树状数组或线段树。

相似题目

题目 难度 考察点
304. 二维区域和检索 - 矩阵不可变 中等 二维版本，查询要用容斥原理做四项加减，边界同样靠多开一行一列消掉
307. 区域和检索 - 数组可修改 中等 允许单点更新，前缀和失效，必须换成树状数组或线段树
560. 和为 K 的子数组 中等 同样把区间和写成前缀差，但要配合哈希表反查，目标是统计方案数
724. 寻找数组的中心下标 简单 左右两侧和相等，用一个总和减去左前缀即可，无需完整前缀数组
238. 除了自身以外数组的乘积 中等 把前缀和换成前缀积并配合后缀积，且不许用除法，考察同一套预处理思想
1310. 子数组异或查询 中等 运算换成异或，因其自逆性同样支持「前缀相消」，是前缀技巧的推广
1109. 航班预订统计 中等 反向操作：多次区间加、最后一次性查询，用差分数组再求前缀和
370. 区间加法 中等 纯差分数组模板题，正好与本题构成「前缀和与差分互逆」的一对