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] <= 1050 <= i <= j < nums.length104 次 sumRange 方法原站题解
php 解法, 执行用时: 23 ms, 内存消耗: 24.4 MB, 提交时间: 2024-03-18 10:08:01
class NumArray {
/**
* @param Integer[] $nums
*/
function __construct($nums) {
$this->sums = [0];
foreach ( $nums as $i => $num ) {
array_push($this->sums, $num + $this->sums[$i]);
}
}
/**
* @param Integer $left
* @param Integer $right
* @return Integer
*/
function sumRange($left, $right) {
return $this->sums[$right+1] - $this->sums[$left];
}
}
/**
* Your NumArray object will be instantiated and called as such:
* $obj = NumArray($nums);
* $ret_1 = $obj->sumRange($left, $right);
*/
python3 解法, 执行用时: 62 ms, 内存消耗: 20.4 MB, 提交时间: 2024-03-18 10:02:01
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]
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(left,right)
golang 解法, 执行用时: 20 ms, 内存消耗: 8.1 MB, 提交时间: 2024-03-18 10:01:48
type NumArray struct {
sums []int
}
func Constructor(nums []int) NumArray {
sums := make([]int, len(nums)+1)
for i, v := range nums {
sums[i+1] = sums[i] + v
}
return NumArray{sums}
}
func (na *NumArray) SumRange(i, j int) int {
return na.sums[j+1] - na.sums[i]
}
/**
* Your NumArray object will be instantiated and called as such:
* obj := Constructor(nums);
* param_1 := obj.SumRange(left,right);
*/
java 解法, 执行用时: 7 ms, 内存消耗: 48.2 MB, 提交时间: 2024-03-18 10:01:25
class NumArray {
int[] sums;
public NumArray(int[] nums) {
int n = nums.length;
sums = new int[n + 1];
for (int i = 0; i < n; i++) {
sums[i + 1] = sums[i] + nums[i];
}
}
public int sumRange(int i, int j) {
return sums[j + 1] - sums[i];
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(left,right);
*/
golang 解法, 执行用时: 17 ms, 内存消耗: 8.6 MB, 提交时间: 2024-03-18 10:01:01
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 单独讨论了
}
/**
* Your NumArray object will be instantiated and called as such:
* obj := Constructor(nums);
* param_1 := obj.SumRange(left,right);
*/
golang 解法, 执行用时: 65 ms, 内存消耗: 8.3 MB, 提交时间: 2024-03-18 09:59:46
type NumArray struct {
nums []int
}
func Constructor(nums []int) NumArray {
return NumArray{
nums:nums,
}
}
func (this *NumArray) SumRange(left int, right int) int {
ans := 0
for i := left; i <= right; i++ {
ans += this.nums[i]
}
return ans
}
/**
* Your NumArray object will be instantiated and called as such:
* obj := Constructor(nums);
* param_1 := obj.SumRange(left,right);
*/
php 解法, 执行用时: 403 ms, 内存消耗: 24.6 MB, 提交时间: 2024-03-18 09:56:59
class NumArray {
/**
* @param Integer[] $nums
*/
function __construct($nums) {
$this->nums = $nums;
}
/**
* @param Integer $left
* @param Integer $right
* @return Integer
*/
function sumRange($left, $right) {
return array_sum(array_slice($this->nums, $left, $right - $left + 1));
}
}
/**
* Your NumArray object will be instantiated and called as such:
* $obj = NumArray($nums);
* $ret_1 = $obj->sumRange($left, $right);
*/
python3 解法, 执行用时: 1504 ms, 内存消耗: N/A, 提交时间: 2018-08-31 14:57:09
class NumArray:
def __init__(self, nums):
"""
:type nums: List[int]
"""
self.nums = nums
def sumRange(self, i, j):
"""
:type i: int
:type j: int
:rtype: int
"""
return sum(self.nums[i:j+1])
# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)