303-区域和检索 - 数组不可变(Range Sum Query - Immutable)

原文链接: https://leetcode-cn.com/problems/range-sum-query-immutable

英文原文

Given an integer array nums, handle multiple queries of the following type:

Calculate the sum of the elements of nums between indices left and right inclusive where left <= right.

Implement the NumArray class:

NumArray(int[] nums) Initializes the object with the integer array nums.
int sumRange(int left, int right) Returns the sum of the elements of nums between indices left and right inclusive (i.e. nums[left] + nums[left + 1] + ... + nums[right]).

Example 1:

Input
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output
[null, 1, -1, -3]

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

Constraints:

1 <= nums.length <= 10⁴
-10⁵ <= nums[i] <= 10⁵
0 <= left <= right < nums.length
At most 10⁴ calls will be made to sumRange.

中文题目

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

通过代码

高赞题解

本文将从暴力法出发，逐步思考优化的点，最后过渡到前缀和的引入，看看前缀和到底优化了什么。

暴力法

每次调用 sumRange 时，都遍历 i 到 j 之间的元素，进行累加。

[]

func sumRange(i, j) {

    var sum = 0

    for i 到 j {

        sum += 当前元素;

    }

    return sum

}

时间复杂度 O(n)，看起来挺好，存在什么问题？

如果 sumRange 方法被反复调用，每次都是 O(n)，「查询」的代价有点大

第一步优化

我想在初始化 NumArray 时就计算好所有的sumRange(i, j)的结果，对应存给res[i][j]

这样「查询」就只用付出 $O(1)$ 的代价

开了一个二维数组，空间复杂度变成 $O(n^2)$

求出所有的sumRange(i,j)，需要三重循环，$O(n^3)$

遍历 i
- 遍历 j
  - 从 i 到 j 的元素累加求和

[]

func initRes(i, j) {

    var res [][]int

    for i 从 0 到 数组末尾 {

        for j 从 i 到 数组末尾 {

            for 从 i 到 j {

                res[i][j] += 当前元素

            }

        }

    }

    return res

}

第二步优化

内层循环累加求和时：上轮迭代求了 i 到 j - 1 的和，这轮就没必要从头求 i 到 j 的和。

去掉内层循环，用一个变量保存上次的求和结果，每次累加当前项即可。

[]

func initRes(i, j) {

    var res [][]int

    for i 从 0 到 数组末尾 {

        var sum = 0

        for j 从 i 到 数组末尾 {

            sum += 当前元素

            res[i][j] = sum

        }

    }

    return res

}

初始化时：时间复杂度 $O(n^2)$ 了，空间复杂度 $O(n^2)$。

查询时：$O(1)$。

还能再优化吗？时间复杂度我想再降一下。

第三步优化，引入前缀和

nums 数组的每一项都对应有它的前缀和： nums 的第 0 项到当前项的和。
用数组 preSum 表示，$preSum[i]$：第 0 项到第 i 项的和。

$$preSum[i] = nums[0] + nums[1] +…+nums[i]$$

易得，nums 的某项 = 两个相邻前缀和的差：

$$nums[i] = preSum[i] - preSum[i - 1]$$

对于 nums 的 i 到 j 的元素和，上式叠加，有：

$$nums[i] +…+nums[j]=preSum[j] - preSum[i - 1]$$

当 i 为 0 时，此时 i-1 为 -1，我们故意让preSum[-1]为 0，使得上式在i=0时也成立：

$$nums[0] +…+nums[j]=preSum[j]$$

所以： $sumRange(i, j)=preSum[j] - preSum[i - 1]$

我们在初始化阶段求出preSum数组的每一项，求sumRange(i,j)时直接返回preSum[j] - preSum[i-1]

怎么求 preSum 数组

利用前面提到的递推式:

$$preSum[i] = preSum[i - 1]+nums[i]$$

遍历求出每一个preSum[i]，别忘了预置preSum[-1]为0，即preSum[0]为nums[0]（前提是nums有元素）。

预置preSum[-1]这种荒谬的情况，只是为了边界情况也能套用通式。

代码 v1

先别觉得下面代码长，顺着思路这么写下来，对我来说是直觉的。

只是需要针对len(nums)==0的情况进行特判，i = 0 的情况，也需单独讨论。

后面会给出简化的写法。

[]

type NumArray struct { // 维护了preSum数组和nums数组的长度

	preSum  []int

	numsLen int

}



func Constructor(nums []int) NumArray {

	if len(nums) == 0 { // nums数组没有元素 就不能preSum[0] = nums[0] 这么写

		return NumArray{

			preSum:  []int{},

			numsLen: 0,

		}

	}

	nA := NumArray{ // nums数组有元素，创建NumArray

		preSum:  make([]int, len(nums)), // 每个元素对应一个前缀和，所以preSum和nums等长

		numsLen: len(nums),

	}

	nA.preSum[0] = nums[0] // 预置边界情况

	for i := 1; i < len(nums); i++ {

		nA.preSum[i] = nA.preSum[i-1] + nums[i] // 套用递推式 求出preSum[i]

	}

	return nA

}



func (this *NumArray) SumRange(i int, j int) int {

	if i == 0 { // 此时preSum[i-1]应该为0，从0到j的求和，应该返回preSum[j]

		if this.numsLen == 0 { // 但如果nums根本没有长度，直接返回0

			return 0

		}

		return this.preSum[j]

	}

	return this.preSum[j] - this.preSum[i-1] // 非i=0情况，套用通式

}

简化写法

之所以上面处理东西多，是因为preSum[i]的定义导致的

我们希望改成：

$$nums[i] +…+nums[j]=preSum[j+1] - preSum[i]$$

于是，我们将preSum[i]定义改成：

$$preSum[i+1] = nums[0] + nums[1] +…+nums[i]$$

则有：

$$nums[i] = preSum[i+1] - preSum[i ]$$

则有：

$$nums[i] +…+nums[j]=preSum[j+1] - preSum[i]$$

即：$sumRange(i, j)=preSum[j+1] - preSum[i]$

当 i = 0 时，只有让preSum[0]为0，才能让通式成立：nums[0]+…+nums[j]=preSum[j+1]

代码v2

[]

type NumArray struct {  // 维护了preSum数组

    preSum []int

}



func Constructor(nums []int) NumArray {

    nA := NumArray{    

		preSum: make([]int, len(nums)+1),// nums[i]对应的前缀和是preSum[i+1] preSum长度加了1

	}

    nA.preSum[0] = 0

    for i := 0; i < len(nums); i++ {

        nA.preSum[i+1] = nA.preSum[i] + nums[i]

    }

    return nA

}



func (this *NumArray) SumRange(i int, j int) int {

    return this.preSum[j+1] - this.preSum[i] // 不用针对 i=0 单独讨论了

}

[]

var NumArray = function (nums) {

    const preSum = new Array(nums.length + 1);

    preSum[0] = 0;

    for (let i = 0; i < nums.length; i++) {

        preSum[i + 1] = preSum[i] + nums[i];

    }

    this.preSum = preSum;

};



NumArray.prototype.sumRange = function (i, j) {

    return this.preSum[j + 1] - this.preSum[i];

};

复盘总结

引入「前缀和」，将预处理阶段（初始化）的时间复杂度降为 $O(n)$，空间复杂度为 $O(n)$

至少在预处理时不用去到 $O(n^2)$ $O(n^3)$ 的时间复杂度

更重要的是，后续的每次「查询」，时间复杂度都是 $O(1)$。

回顾讲过的例子，综合比较一下：

每次查询：Time： $O(n)$
初始化时：Time：$O(n^3)$， Space：$O(n^2)$ ，查询：Time：$O(1)$。
初始化时：Time： $O(n^2)$， Space： $O(n^2)$，查询：Time：$O(1)$。
初始化时：Time： $O(n)$， Space： $O(n)$，查询：Time：$O(1)$。——应用前缀和

其实前缀和经常用于对数组做预处理，将题目做等价转化成求 preSum 的问题

降低查询时的时间复杂度。在处理子数组求和时很好用。

结合题意要求，有时候甚至不用求出 preSum 数组的每一项

因为我们可能根本不关心 preSum 们对应了具体哪一项 nums[i]

可能我们只关心出现过哪些 preSum ，我是联想到《560题.和为K的子数组》了

如果觉得不错就点个赞鼓励一下吧，

统计信息

通过次数	提交次数	AC比率
134853	184840	73.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
二维区域和检索 - 矩阵不可变	中等
区域和检索 - 数组可修改	中等
和等于 k 的最长子数组长度	中等

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途