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

给定一个整数数组 nums，处理以下类型的多个查询:

计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right 实现 NumArray 类：

NumArray(int[] nums) 使用数组 nums 初始化对象 int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] ）

示例 1:
输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]

解题思路

输入：一个整数数组 nums

输出：一个 Array 类，能够高效计算数组中索引 left 到 right（包含两端）的元素总和

本题属于一维前缀和问题。

我们可以预计算前缀和数组 pre_sum，其中 pre_sum[i] 表示 nums 从索引 0 到 i-1 的元素之和。

查询区间 [left, right] 的和时，利用公式 pre_sum[right + 1] - pre_sum[left] 快速计算 nums[left] 到 nums[right] 的总和。

代码实现

python

class NumArray:
    def __init__(self, nums: List[int]):
        # 初始化前缀和数组，第一个元素为 0，表示空数组的和
        self.pre_sum = [0]
        # 遍历输入数组，计算前缀和
        for num in nums:
            # 当前前缀和 = 上一个前缀和 + 当前数字
            self.pre_sum.append(self.pre_sum[-1] + num)

    def sumRange(self, left: int, right: int) -> int:
        # 使用前缀和公式计算区间和：pre_sum[right+1] - pre_sum[left]
        # 返回 nums[left] 到 nums[right] 的和
        return self.pre_sum[right + 1] - self.pre_sum[left]

javascript

// 构造函数：初始化时传入原数组 nums
const NumArray = function(nums) {
    // 创建前缀和数组，初始为 [0]
    // preSum[i] 表示 nums[0] 到 nums[i - 1] 的总和
    this.preSum = [0];

    // 构建前缀和数组，注意从 1 开始填充
    for (let num of nums) {
        // 当前项 = 上一项前缀和 + 当前数
        this.preSum.push(this.preSum.at(-1) + num);
    }
};

// 实现 sumRange(left, right)：返回区间 [left, right] 的和
NumArray.prototype.sumRange = function(left, right) {
    // 区间和 = preSum[right + 1] - preSum[left]
    return this.preSum[right + 1] - this.preSum[left];
};

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

链接

303 国际版

303 中文版