力扣链接：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 (-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
约束:
1 <= nums.length <= 10^4-10^5 <= nums[i] <= 10^50 <= left <= right < nums.length- 最多调用
10^4次sumRange方法
思路
- 使用新数组
prefix_sums保存前面元素的总和。 prefix_sums的第一个元素为0，因为前缀和 不包含当前元素。- 要查找从索引
left到right（含）元素的总和，只需使用prefix_sums[right + 1] - prefix_sums[left]。
复杂度
时间复杂度
O(N)
空间复杂度
O(N)
Java #
class NumArray {
private int[] prefixSums;
public NumArray(int[] nums) {
prefixSums = new int[nums.length + 1];
var sum = 0;
for (var i = 0; i < nums.length; i++) {
sum += nums[i];
prefixSums[i + 1] = sum;
}
}
public int sumRange(int left, int right) {
return prefixSums[right + 1] - prefixSums[left];
}
}
Python #
class NumArray:
def __init__(self, nums: List[int]):
self.prefix_sums = [0]
sum_ = 0
for num in nums:
sum_ += num
self.prefix_sums.append(sum_)
def sumRange(self, left: int, right: int) -> int:
return self.prefix_sums[right + 1] - self.prefix_sums[left]
C++ #
class NumArray {
private:
vector<int> prefixSums;
public:
NumArray(vector<int>& nums) {
prefixSums.push_back(0);
auto sum = 0;
for (auto num : nums) {
sum += num;
prefixSums.push_back(sum);
}
}
int sumRange(int left, int right) {
return prefixSums[right + 1] - prefixSums[left];
}
};
JavaScript #
let prefixSums
var NumArray = function (nums) {
prefixSums = [0]
let sum = 0
nums.forEach((num) => {
sum += num
prefixSums.push(sum)
})
};
NumArray.prototype.sumRange = function (left, right) {
return prefixSums[right + 1] - prefixSums[left]
};
C# #
public class NumArray
{
int[] prefixSums;
public NumArray(int[] nums)
{
prefixSums = new int[nums.Length + 1];
int sum = 0;
for (int i = 0; i < nums.Length; i++)
{
sum += nums[i];
prefixSums[i + 1] = sum;
}
}
public int SumRange(int left, int right)
{
return prefixSums[right + 1] - prefixSums[left];
}
}
Go #
type NumArray struct {
prefixSums []int
}
func Constructor(nums []int) NumArray {
prefixSums := make([]int, len(nums) + 1)
sum := 0
for i, num := range nums {
sum += num
prefixSums[i + 1] = sum
}
return NumArray{prefixSums}
}
func (this *NumArray) SumRange(left int, right int) int {
return this.prefixSums[right + 1] - this.prefixSums[left]
}
Ruby #
class NumArray
def initialize(nums)
@prefix_sums = [0]
sum = 0
nums.each do |num|
sum += num
@prefix_sums << sum
end
end
def sum_range(left, right)
@prefix_sums[right + 1] - @prefix_sums[left]
end
end
其它语言
欢迎贡献代码到我们的 GitHub 仓库，非常感谢！本题解位置在 303. 区域和检索 - 数组不可变。题解2的思路：直接返回数组区域内值之和（慢）
直接返回数组区域内值之和，虽然可以通过测试，但是如果测试用例更严格的话就会失败。
所以我们还需要学习一种更有效的解决方案：前缀和方案。
复杂度
时间复杂度
O(M * N)
空间复杂度
O(M * N)
Python #
class NumArray:
def __init__(self, nums: List[int]):
self.nums = nums
def sumRange(self, left: int, right: int) -> int:
return sum(self.nums[left:right + 1])