20210301 LeetCode 每日一题，冲！｜刷题打卡

为了准备校招，这两个个月俺也在 Leetcode 上开始慢慢刷起了一些算法题。从一开始的 eay 都要看题解，到现在可以自己攻破大多数 medium，偶尔也能冲一下 hard，感觉多少是有些进步的。我也在 GitHub 上开了个 JavaScript 写算法的 repo，前端的小伙伴可以来捧个场噢！

GitHub 链接：LeetCode-JavaScript

题目描述

Leetcode 链接：303 区域和检索 - 数组不可变（easy）

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

实现 NumArray 类：

• NumArray(int[] nums) 使用数组 nums 初始化对象
• int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）

示例：

输入：
["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))

提示：

• 0 <= nums.length <= 104
• -105 <= nums[i] <= 105
• 0 <= i <= j < nums.length
• 最多调用 104 次 sumRange 方法

JavaScript 模板：

/**
 * @param {number[]} nums
 */
var NumArray = function(nums) {
};

/** 
 * @param {number} i 
 * @param {number} j
 * @return {number}
 */
NumArray.prototype.sumRange = function(i, j) {
};

/**
 * Your NumArray object will be instantiated and called as such:
 * var obj = new NumArray(nums)
 * var param_1 = obj.sumRange(i,j)
 */

思路分析

因为这个奇怪的示例，所以我乍一看这题还以为它很复杂的样子，不过仔细看一下的话就会发现这道题目确实世道 easy 题。啊不对，是 very easy 的题了。我们只需要完成两个步骤即可：

1. 使用 NumArray 来初始化 nums 数组。这一步我确实没想到其背后有什么深奥的含义，就直接为其增加了一个表示该 nums 数组的 array 属性。创建时的时间复杂度为 O(1)：

var NumArray = function(nums) {
  this.array = nums;
};

2. 在调用 sumRange 方法时返回范围内的元素和。这一步乍一看也没什么难度，我就用 reduce 定义了一个求和的方法，调用时的时间复杂度为 O(n)：

NumArray.prototype.sumRange = function(i, j) {
  return this.array.slice(i,j+1).reduce((a,b) => a+b);
};

然后。。。然后就没有然后了 - -！我又读了下题目，发现确实没有别的需求了，我便怀着忐忑的心提交了，没想到啊没想到啊，只花了两分钟的题解居然一次就过了：

阿等等，这个执行用时是什么情况 - -！

优化一下

不一会儿，我就发现了这个耗时的问题，就出在这个时间复杂度为 O(n) 的求和方法上，我们有什么办法来降低其复杂度呢？我发现了在初始化的部分，我们其实可以进行一些更多的操作，然后来让查询的部分变得更为简单:

我们可以在初始化时，维护一个用于记录前缀和的数组，而非原数组本身，这样一来，初始化的时间复杂度就变成了 O(n)：

var NumArray = function(nums) {
  let length = nums.length;
  this.preSum = new Array(length + 1).fill(0); // 初始化前缀和数组
  for (let i = 0; i < length; i++) {
    this.preSum[i+1] = this.preSum[i] + nums[i]; // 为元素赋值
  }
};

不过在查询时，我们只需要计算 j+1 和 i 的前缀和之差就行了，所以时间复杂度则变成了 O(1)：

NumArray.prototype.sumRange = function(i, j) {
  return this.preSum\[j+1\] - this.preSum\[i\];
};

这样一来就得到了一个正常的时间复杂度啦 ψ(｀∇´)ψ

总结一下

通过在初始化时进行更多一些的操作，我们成功的将查询的时间复杂度从 O(n) 降到了 O(1)。不过总的来说，这还是一道 very easy 的题目。

不过就 LeetCode 的德行，这个月第一题这么水就意味着后面的题目会贼难，希望不要有题目把我卡死在打卡的路上吧！三月，冲！

最后再 po 一下俺的 GitHub ：LeetCode-JavaScript 欢迎互粉互 star！ヾ(•ω•`)o