leetcode 303 区域和检索 - 数组不可变

zhaojun

2023 年 01 月 27 日

1036 次浏览

暂无评论

190字数

默认分类

https://leetcode.cn/problems/range-sum-query-immutable/description/

## 题目

给定一个整数数组  `nums`，处理以下类型的多个查询:

1.  计算索引 `left` 和 `right` （包含 `left` 和 `right`）之间的 `nums` 元素的 **和** ，其中 `left <= right`

实现 `NumArray` 类：

-   `NumArray(int[] nums)` 使用数组 `nums` 初始化对象
-   `int sumRange(int i, int j)` 返回数组 `nums` 中索引 `left` 和 `right` 之间的元素的 **总和** ，包含 `left` 和 `right` 两点（也就是 `nums[left] + nums[left + 1] + ... + nums[right]` )

**示例 1：**

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

**提示：**

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

## 思路

### 暴力法

暴力法即将传入的 nums 赋值给成员变量，每次调用 sumRange 时，从 left 到 right 遍历取出元素进行累加。不过这样  `sumRange` 方法的时间复杂度为 $O(n)$

### 前缀和

可以提前算出每个位置的累计和，然后用 right 处的累计和，减去 left 左侧不需要的累计和即可。

如：
```java
nums = [1, 2, 3, 4, 5]

// 累计和: sums[i - 1] 就是 nums 0 - i 的累计和。
sums = [0, 1, 3, 6, 10, 15]
```

## 代码

### 暴力法
```java
class NumArray {

private int[] nums;

public NumArray(int[] nums) {
        this.nums = nums;
    }
    
    public int sumRange(int left, int right) {
        int sum = 0;
        for (int i = left; i <= right; i++) {
            sum += this.nums[i];
        }

return sum;
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(left,right);
 */
```

### 前缀和

```java
class NumArray {

private int[] sums;

public NumArray(int[] nums) {
        int n = nums.length;
        sums = new int[n + 1];
        for (int i = 0; i < n; i++) {
            sums[i + 1] = sums[i] + nums[i];
        }
    }
    
    public int sumRange(int left, int right) {
        return sums[right + 1] - sums[left];
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(left,right);
 */
```

最后修改：2023 年 01 月 27 日

如果觉得我的文章对你有用，请我喝杯咖啡吧。

leetcode 303 区域和检索 - 数组不可变

zhaojun • 2023 年 01 月 27 日

leetcode 303 区域和检索 - 数组不可变

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

谈裸辞和开源的体会

剑指 Offer 04. 二维数组中的查找

Shiro 学习 04 - 加密

通过 Github Actions 自动构建 ZFile 镜像并推送到 Docker Hub

优化 Java 项目 Docker 镜像内存占用从 500 M 到 100M

中文文案排版指北「转载」

leetcode 409 最长回文串

手撸 Java Web RBAC 权限管理

MySQL InnoDB 事务隔离级别的实现原理

Spring MVC/Boot 统一异常处理最佳实践

leetcode 303 区域和检索 - 数组不可变

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

leetcode 303 区域和检索 - 数组不可变

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款