[303][简单][动态规划][前缀和] 区域和检索 - 数组不可变

题目描述

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

给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。

实现 NumArray 类：

NumArray(int[] nums) 使用数组 nums 初始化对象 int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）

示例：

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

解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

提示：

• 0 <= nums.length <= 104

• -105 <= nums[i] <= 105

• 0 <= i <= j < nums.length

• 最多调用 104 次 sumRange 方法

解题思路

使用前缀和, 记录包含当前位置数字在内的, 之前所有数字的和. 求前缀和使用动态规划的方法. 在得到前缀和之后, 求任意两点之间的元素总和, 就可以使用对应的前缀和相减得到.

有个技巧是在存储前缀和的列表中, 在最前面的位置添加一个0, 这样在求前缀和之差的时候, 就不用考虑边界情况, 减少了代码的复杂度.

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, i: int, j: int) -> int:
        return self.prefix[j + 1] - self.prefix[i]

相关题目

• [304][中等][动态规划][前缀和] 二维区域和检索 - 矩阵不可变