LeetCode 303. 区域和检索 - 数组不可变
题目描述
题意分析
初始化一个数组后，需要多次查询闭区间
[left,right]的元素和，两个端点都包含在内。查询之间没有修改操作，因此可以在构造时统一预处理，避免每次重新遍历区间。
解法：前缀和
核心思路
[!blue]
定义
prefix[i]为前i个元素的和，也就是下标区间[0,i)的和。于是prefix[0]=0表示空前缀，并且prefix[i+1]=prefix[i]+nums[i]。从左到右计算时，每个新前缀只在上一个正确的前缀和后追加一个元素，因此一次遍历就能得到全部前缀和。查询
[left,right]时，prefix[right+1]包含从下标0到right的全部元素，prefix[left]只包含left之前的元素。两者相减恰好去掉共同的左侧部分，留下nums[left]到nums[right]，所以答案是prefix[right+1]-prefix[left]。多出的零号项统一了边界：
left=0时减去的就是0；left=right时相邻两个前缀之差恰好是一个元素；right=n-1时可以直接访问prefix[n]。这个推导只用加减法，数组含负数也同样成立。
解题步骤
- 创建长度为
nums.length + 1的前缀和数组。- 对每个下标
i，计算prefix[i+1] = prefix[i] + nums[i]。- 查询
[left, right]时返回prefix[right+1] - prefix[left]。题目保证查询下标合法。按给定长度和元素范围，任意前缀或区间和的绝对值不超过
10^9，现有整型实现可以容纳。
代码实现
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)$；若查询
q次，总时间为 $O(n+q)$。- 空间复杂度：$O(n)$，用于保存前缀和数组。
关键点总结
[!green]
- 数组不变，预处理得到的前缀和可以被全部查询复用。
- 前缀下标表示元素数量，查询的右端点需要转换成
right+1。- 区间和由两个前缀的公共部分相减得到，不要求元素非负。
易错点总结
[!yellow]
- 使用
prefix[right]会漏掉右端点；减去prefix[left+1]会连左端点一起去掉。- 当前定义需要长度为
n+1的数组，才能同时保存空前缀和完整数组的和。- 每次查询重新累加会失去预处理的意义；这里也没有修改操作，无需维护动态区间结构。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 304. 二维区域和检索 - 矩阵不可变 | 中等 | 把一维前缀和推广到二维，需要用四个角做矩形容斥。 |
| 307. 区域和检索 - 数组可修改 | 中等 | 加入单点修改后静态前缀和更新昂贵，需树状数组或线段树维护。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！