84 - 区域和检索- 数组不可变

题目

给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。

示例：

给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()

sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3

说明:

1. 你可以假设数组不可变。

2. 会多次调用 sumRange 方法。

解答

就，加起来咯。。

/**
 * @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.

？？？这么简单的吗？？

https://leetcode-cn.com/problems/range-sum-query-immutable/solution/48mssan-chong-fang-fa-de-go-shi-xian-by-elliotxx/

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);
}

go:

func main() {
    obj := Constructor([]int{-2, 0, 3, -5, 2, -1})
    var param_1 = obj.SumRange(0, 2)
    fmt.Println("param_1", param_1)
    var param_2 = obj.SumRange(2, 5)
    fmt.Println("param_2", param_2)
    var param_3 = obj.SumRange(0, 5)
    fmt.Println("param_3", param_3)
}