303. 区域和检索 - 数组不可变
303. 区域和检索 - 数组不可变
题目
Given an integer array nums
, handle multiple queries of the following type:
- Calculate the sum of the elements of
nums
between indicesleft
andright
inclusive whereleft <= right
.
Implement the NumArray
class:
NumArray(int[] nums)
Initializes the object with the integer arraynums
.int sumRange(int left, int right)
Returns the sum of the elements ofnums
between indicesleft
andright
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^4
-10^5 <= nums[i] <= 10^5
0 <= left <= right < nums.length
- At most
104
calls will be made tosumRange
.
题目大意
给定一个整数数组 nums
,请你完成查询:
返回数组 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]
)
解题思路
标准的前缀和问题,核心思路是用一个新的数组 preSum
记录 nums
的累加和,这样,sumRange
函数仅仅需要做一次减法运算,避免了每次进行 for
循环调用,最坏时间复杂度为常数 O(1)
。
复杂度分析
- 时间复杂度:
sumRange
函数的时间复杂度为O(1)
。 - 空间复杂度:
O(n)
,其中n
为nums
数组的长度,使用了一个长度为n
的数组来存储中间状态。
代码
/**
* @param {number[]} nums
*/
class NumArray {
constructor(nums) {
this.preSum = [0];
for (let i = 1; i <= nums.length; i++) {
this.preSum[i] = this.preSum[i - 1] + nums[i - 1];
}
}
/**
* @param {number} left
* @param {number} right
* @return {number}
*/
sumRange(left, right) {
return this.preSum[right + 1] - this.preSum[left];
}
}
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
304 | 二维区域和检索 - 矩阵不可变 | 设计 数组 矩阵 1+ | ||
307 | 区域和检索 - 数组可修改 | [✓] | 设计 树状数组 线段树 1+ | |
325 | 和等于 k 的最长子数组长度 🔒 | 数组 哈希表 前缀和 |