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

🥉Easy

给定一个整数数组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<=
• - <= nums[i] <=
• 0 <= i <= j < nums.length
• 最多调用 次 sumRange 方法

题解

最直观的想法

个人的思路是：存储数组，然后从原数组中截取需要的数组，然后求和。Python写起来比较简单：

Python

class NumArray:

    def __init__(self, nums: List[int]):
        self.data=nums


    def sumRange(self, i: int, j: int) -> int:
        temp = self.data[i:j+1]
        return sum(temp)

# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

JavaScript

var NumArray = function(nums) {
    this.data = nums
};

NumArray.prototype.sumRange = function(i, j) {
    let temp = this.data.slice(i,j+1)
    return temp.reduce((cur,next)=>cur+next)
};

但这样，每次调用sumRange时，都需要计算nums数组从下标i到j的元素和。由于每次检索的时间和检索的下标范围有关，因此检索的时间复杂度较高，如果检索次数较多，则会超出时间限制。

前缀和

因为会多次调用sumRange，为了降低检索总时间，就需要降低sumRange的时间复杂度，上面复杂度为，再降就只能为。

sumRange(i,j)可以通过计算nums在下标j和下标i-1的前缀和之差得到：

在初始的时候，就计算出nums在每个下标处的前缀和，这样sumRange时间复杂度不就变成了!

所以，设长度为，创建长为的前缀和数组，对都有,则当时，表示数组从下标到下标前缀和

因此：

Python

class NumArray:

    def __init__(self, nums: List[int]):
        self.sums = [0]
        _sums = self.sums

        for num in nums:
            _sums.append(_sums[-1] + num)

    def sumRange(self, i: int, j: int) -> int:
        _sums = self.sums
        return _sums[j + 1] - _sums[i]

JavaScript

var NumArray = function(nums) {
    const n = nums.length;
    this.sums = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        this.sums[i + 1] = this.sums[i] + nums[i];
    }
};

NumArray.prototype.sumRange = function(i, j) {
    return this.sums[j + 1] - this.sums[i];
};

复杂度分析

• 时间复杂度：初始化 ，每次检索 ，其中 是数组 的长度。

初始化需要遍历数组 计算前缀和，时间复杂度是 。
每次检索只需要得到两个下标处的前缀和，然后计算差值，时间复杂度是 。

• 空间复杂度：，其中 是数组的长度。需要创建一个长度为的前缀和数组。