题目描述（简单难度）

303、Range Sum Query - Immutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:

Given nums = [-2, 0, 3, -5, 2, -1] sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3 

Note:

1. You may assume that the array does not change.
2. There are many calls to sumRange function.

设计一个类，返回数组的第 i 到 j 个元素的和。

解法一 暴力

题目是想让我们设计一种数据结构，我们先暴力写一下。

/** * @param {number[]} nums */ var NumArray = function(nums) { this.nums = nums; }; /** * @param {number} i * @param {number} j * @return {number} */ NumArray.prototype.sumRange = function(i, j) { let sum = 0; for(; i <= j; i++){ sum += this.nums[i]; } return sum; }; /** * Your NumArray object will be instantiated and called as such: * var obj = new NumArray(nums) * var param_1 = obj.sumRange(i,j) */ 

分享 官方 提供的一个优化，因为是多次调用 sumRange，我们可以在每次调用后将结果保存起来，这样的话第二次调用就可以直接返回了。

/** * @param {number[]} nums */ var NumArray = function(nums) { this.nums = nums; this.map = {}; }; /** * @param {number} i * @param {number} j * @return {number} */ NumArray.prototype.sumRange = function(i, j) { let key = i + '@' + j; if(this.map.hasOwnProperty(key)){ return this.map[key]; } let sum = 0; for(; i <= j; i++){ sum += this.nums[i]; } this.map[key] = sum; return sum; }; /** * Your NumArray object will be instantiated and called as such: * var obj = new NumArray(nums) * var param_1 = obj.sumRange(i,j) */ 

解法二

和 238 题 的解法二有一些像。

我们用一个数组保存累计的和，numsAccumulate[i] 存储 0 到 i - 1 累计的和。

如果我们想求 i 累积到 j 的和，只需要用 numsAccumulate[j + 1] 减去 numsAccumulate[i]。

结合下边的图应该很好理解，我们要求的是橙色部分，相当于 B 的部分减去 A 的部分。

代码也就水到渠成了。

/** * @param {number[]} nums */ var NumArray = function (nums) { this.numsAccumulate = [0]; let sum = 0; for (let i = 0; i < nums.length; i++) { sum += nums[i]; this.numsAccumulate.push(sum); } }; /** * @param {number} i * @param {number} j * @return {number} */ NumArray.prototype.sumRange = function (i, j) { return this.numsAccumulate[j + 1] - this.numsAccumulate[i]; }; /** * Your NumArray object will be instantiated and called as such: * var obj = new NumArray(nums) * var param_1 = obj.sumRange(i,j) */ 

总

比较简单的一道题，解法一做缓存的思路比较常见。解法二的思路印象中也遇到过几次，看到题目我的第一反应想到的就是解法二。