/**
* @param {number[]} nums
*/
var NumArray = function (nums) {
this.data = nums
};
/**
* @param {number} i
* @param {number} j
* @return {number}
*/
NumArray.prototype.sumRange = function (i, j) {
let sum = 0
for (let index = i; index <= j; index++) {
sum += this.data[index]
}
return sum
};
Runtime: 152 ms, faster than 34.90% of JavaScript online submissions for Range Sum Query - Immutable.
Memory Usage: 44 MB, less than 100.00% of JavaScript online submissions for Range Sum Query - Immutable.
？？？这么简单的吗？？
type NumArray struct {
data []int
}
func Constructor(nums []int) NumArray {
a := NumArray{data: nums}
return a
}
func (this *NumArray) SumRange(i int, j int) int {
var sum int
for ; i <= j; i++ {
sum += this.data[i]
}
return sum
}
Runtime: 76 ms, faster than 23.81% of Go online submissions for Range Sum Query - Immutable.
Memory Usage: 8.3 MB, less than 100.00% of Go online submissions for Range Sum Query - Immutable.
这里的for循环很有趣，就直接用了传入的参数，往上加。
go需要一个构造函数，而不能直接new一个新的出来。
感觉js的做法其实和go一样，只不过go需要人写出来这个过程而已。
缓存
把全部计算结果都缓存进哈希表，感觉太可怕了
题解提出了用一个算式来缓存
假设$sum(0)=0$，$sum(k)=nums(0)+nums(1)+…+nums(k-1)$
那么$sumrange(i, j) = sum(j+1)-sum(i)$
/**
* @param {number[]} nums
*/
var NumArray = function (nums) {
this.sum = [0]
for (let i = 0; i < nums.length; i++) {
this.sum[i + 1] = this.sum[i] + nums[i]
}
};
/**
* @param {number} i
* @param {number} j
* @return {number}
*/
NumArray.prototype.sumRange = function (i, j) {
return this.sum[j + 1] - this.sum[i]
};
Runtime: 96 ms, faster than 66.81% of JavaScript online submissions for Range Sum Query - Immutable.
Memory Usage: 44.7 MB, less than 100.00% of JavaScript online submissions for Range Sum Query - Immutable.
好像基本没怎么多花空间么😂
type NumArray struct {
data []int
}
func Constructor(nums []int) NumArray {
sum := make([]int, len(nums)+1)
for i := 0; i < len(nums); i++ {
sum[i+1] = sum[i] + nums[i]
}
return NumArray{data: sum}
}
func (this *NumArray) SumRange(i int, j int) int {
return this.data[j+1] - this.data[i]
}
Runtime: 36 ms, faster than 76.79% of Go online submissions for Range Sum Query - Immutable.
Memory Usage: 11.1 MB, less than 100.00% of Go online submissions for Range Sum Query - Immutable.
测试代码
js:
const test = function () {
var obj = new NumArray([-2, 0, 3, -5, 2, -1])
var param_1 = obj.sumRange(0, 2)
console.log('param_1', param_1);
var param_2 = obj.sumRange(2, 5)
console.log('param_2', param_2);
var param_3 = obj.sumRange(0, 5)
console.log('param_3', param_3);
}