题303-算法

1、描述

给定一个整数数组 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] )

2、提示:

a. 1 <= nums.length <= 104
b. -105 <= nums[i] <= 105
c. 0 <= i <= j < nums.length
d. 最多调用 104 次 sumRange 方法

3、思路

前缀和。
注意到当 left≤right 时，sumRange(left,right) 可以写成如下形式：公式（303-1）.
因此 可以 转为 nums前k个元素和 做差计算，引入sums数组用来记录 前缀和。
考虑到两端下标溢出问题，sums数组 增加 1个元素，即 sums[i] = nums前 i-1 项和，所以公式变为 sums[right+1] - sums[left]。

用前缀和 的方式 代替直接计算 某段和，降低 在多次调用求和方法时的 时间消耗。
用空间 换取 时间。

此外，除了 调用 sums 的 方法来提高效率，再计算 sums 数组时，也可以优化，每次计算 sums[i] = sums[i - 1] + nums[i - 1]，即 通过 迭代方式计算。

$$\text{sumRange}(left,right)=\sum _{k=left}^{right}\text{nums[k]}=\sum _{k=0}^{right}\text{nums[k]}-\sum _{k=0}^{left-1}\text{nums[k]}公式(303-1)$$

4、代码

class NumArray:

    def __init__(self, nums: list[int]):
        self.sums = [0]
        sum = 0
        for num in nums:
            sum += num
            self.sums.append(sum)

    def sumRange(self, left: int, right: int) -> int:
        return self.sums[right + 1] - self.sums[left]
1
2
3
4
5
6
7
8
9
10
11