区域和检索-数组不可变

解题思路：

  1. 先得到前缀和数组 prefixSums；

  2. 数组 arr 的下标范围 [start,end] 的子数组的和为 prefixSums[end+1]−prefixSums[start]；

复杂度：

  1. 时间复杂度：初始化 O(n)，每次检索 O(1)；

  2. 空间复杂度：O(n)，其中 n 是数组 nums 的长度；

代码实现：

var NumArray = function (nums) {
  const n = nums.length;
  // 前缀和
  this.prefixSums = new Array(n + 1).fill(0);

  for (let i = 0; i < n; i++) {
    this.prefixSums[i + 1] = this.prefixSums[i] + nums[i];
  }
};

NumArray.prototype.sumRange = function (left, right) {
  return this.prefixSums[right + 1] - this.prefixSums[left]
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
评论

中午好👏🏻，我是 ✍🏻   疯狂 codding 中...

粽子

这有关于前端开发的技术文档和你分享。

相信你可以在这里找到对你有用的知识和教程。

了解更多

目录

  1. 1. 区域和检索-数组不可变
  2. 2. 解题思路：
  3. 3. 复杂度：
  4. 4. 代码实现：