题目描述(简单难度)

303、Range Sum Query - Immutable

Given an integer array nums, find the sum of the elements between indices i and j (ij), 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.

设计一个类,返回数组的第 ij 个元素的和。

解法一 暴力

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

/**
 * @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] 存储 0i - 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)
 */

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

results matching ""

    No results matching ""