LeetCode 303简单前缀和
区域和检索 - 数组不可变 图解题解
这道题到底在问什么
给定一个整数数组 nums，处理多个查询：计算索引 left 和 right（包含 left 和 right）之间的 nums 元素之和，其中 left <= right。实现 NumArray 类：NumArray(int[] nums) 使用数组 nums 初始化对象；int sumRange(int left, int right) 返回数组 nums 中索引 left 和 right 之间的元素总和。
- 输入
- ["NumArray","sumRange","sumRange","sumRange"]
- 参数
- [[[-2,0,3,-5,2,-1]],[0,2],[2,5],[0,5]]
- 输出
- [null,1,-1,-3]
- 解释
- sumRange(0,2) = -2+0+3 = 1；sumRange(2,5) = 3-5+2-1 = -1；sumRange(0,5) = -3。
最优解：一步一步想明白
- 3题目说要处理多个查询，这就是提示：可以把重复计算提前到初始化阶段。
- 4prefix[0]=0 是哨兵位。它让从 0 开始的区间也能用同一个公式，不需要单独写 if left==0。
- 5self.prefix = [0]第二行是 prefix 数组。第 0 格先放 0，意思是“前 0 个数的和”。
- 6prefix.append(prefix[-1] + x)第一行第 1 列对应 nums[0]。把它加到上一格 prefix[0] 上，得到 prefix[1]。
- 7prefix.append(prefix[-1] + x)prefix[i] 永远表示前 i 个数的和，所以 prefix[2] 覆盖 nums[0..1]。
- 8prefix.append(prefix[-1] + x)到这里，nums[0..2] 的和已经存在 prefix[3] 里，后面查询 [0,2] 会直接用它。
- 9prefix.append(prefix[-1] + x)数组里有负数也没关系，前缀和照样只是普通加法。
- 10prefix.append(prefix[-1] + x)初始化阶段只顺序扫一遍 nums，每个元素只处理一次。
- 11prefix.append(prefix[-1] + x)最终 prefix=[0,-2,-2,1,-4,-2,-3]。构造函数结束后，所有查询都只看这张表。
- 12return prefix[right + 1] - prefix[left]要求 nums[0..2]，右边界要变成 right+1，所以取 prefix[3]；左边界之前没有元素，所以减 prefix[0]。
- 13return prefix[right + 1] - prefix[left]prefix[6] 是 nums[0..5] 的总和；减掉 prefix[2]，就把 nums[0..1] 切掉，只剩 nums[2..5]。
- 14return prefix[right + 1] - prefix[left]从 0 开始的区间也不用特殊处理，因为 prefix[0]=0 正好代表“左边没有要切掉的数”。
- 17这题把“多次区间查询”变成了“初始化多做一点、查询少做很多”。
⚠️ 容易写错的地方
✗ 错：prefix 长度写成 n
✓ 对：prefix 长度应为 n+1，并让 prefix[0]=0
这样 [0,right] 也能直接用统一公式。
✗ 错：用 prefix[right] - prefix[left]
✓ 对：用 prefix[right+1] - prefix[left]
prefix[i] 表示前 i 个元素，right 是包含端点，所以要取 right+1。
✗ 错：每次查询重新 for 循环求和
✓ 对：查询时只做一次减法
多次查询场景下，预处理前缀和才是这题的重点。
✗ 错：担心负数破坏前缀和
✓ 对：负数照样可以累加和相减
前缀和只依赖加法，不要求数组非负。
完整代码（Python）
Python
class NumArray:
def __init__(self, nums):
self.prefix = [0]
for x in nums:
self.prefix.append(self.prefix[-1] + x)
def sumRange(self, left, right):
return self.prefix[right + 1] - self.prefix[left]复杂度
初始化时间
O(n)
构造 NumArray 时扫描 nums 一次，建立 prefix。
单次查询时间
O(1)
sumRange 只读取 prefix[right+1] 和 prefix[left]。
空间复杂度
O(n)
额外保存长度为 n+1 的前缀和数组。
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 区域和检索 - 数组不可变 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「前缀和」，换最直接的暴力解会差在哪？+
前缀和抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。