区域和检索 - 数组不可变

🟢 Easy · 🏷️ 数组、前缀和、设计 · LeetCode#303

📖 题目

实现一个类，支持对同一个数组多次查询区间和。

nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) → 1
sumRange(2, 5) → -1

💡 思路

暴力法每次查询都要现算，O(n)；题目会查很多次，暴力法总时间扛不住。

数组本身不变、要查很多次——这种场景适合预处理：提前算出"从头到每个位置的累加和"，也就是前缀和数组，每次查询就变成两个前缀和相减，O(1)。

prefix[i] 表示 nums 前 i 个元素的和（prefix[0] = 0 是哨兵）。区间 [left, right] 的和就是 prefix[right+1] - prefix[left]。

💻 代码

class NumArray:
    def __init__(self, nums: List[int]):
        self.prefix = [0]
        for num in nums:
            self.prefix.append(self.prefix[-1] + num)

    def sumRange(self, left: int, right: int) -> int:
        return self.prefix[right + 1] - self.prefix[left]

初始化 O(n)，每次查询 O(1)——空间换时间。