友情支持
如果您觉得这个笔记对您有所帮助,看在D瓜哥码这么多字的辛苦上,请友情支持一下,D瓜哥感激不尽,😜
有些打赏的朋友希望可以加个好友,欢迎关注D 瓜哥的微信公众号,这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi 。因为众所周知的原因,有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
303. 区域和检索 - 数组不可变
给定一个整数数组 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]
)
示例 1:
输入: ["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))
提示:
-
1 <= nums.length <= 104
-
-105 <= nums[i] <= 105
-
0 <= i <= j < nums.length
-
最多调用
104
次sumRange
方法
思路分析
前缀和


-
一刷
-
二刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-04 16:46:40
*/
class NumArray {
int[] sums;
public NumArray(int[] nums) {
sums = new int[nums.length + 1];
int sum = 0;
sums[0] = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
sums[i + 1] = sum;
}
}
public int sumRange(int left, int right) {
return sums[right + 1] - sums[left];
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-09-07 18:14:41
*/
class NumArray {
int[] sums;
public NumArray(int[] nums) {
sums = new int[nums.length + 1];
for (int i = 1; i < sums.length; i++) {
sums[i] = sums[i - 1] + nums[i - 1];
}
}
public int sumRange(int left, int right) {
return sums[right + 1] - sums[left];
}
}