区域和检索 - 数组不可变

难度:

标签:

题目描述

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

计算索引 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 <= 10⁴
-10⁵ <= nums[i] <= 10⁵
0 <= i <= j < nums.length
最多调用 10⁴ 次 sumRange 方法

代码结果

运行时间: 60 ms, 内存: 20.0 MB

// Java Solution using Java Stream
 
// 题目思路：
// 我们可以利用 Java Stream API 提供的工具来简化计算。尽管这种方法可能不会有前缀和数组的高效，
// 但可以利用 Stream 的特性进行元素的累加计算。
 
import java.util.Arrays;
 
public class NumArrayStream {
    private int[] nums;
 
    // 构造函数，保存数组
    public NumArrayStream(int[] nums) {
        this.nums = nums;
    }
 
    // 计算区间 [left, right] 的元素和
    public int sumRange(int left, int right) {
        return Arrays.stream(nums, left, right + 1).sum();
    }
}

解释

方法:

这个题解使用了前缀和的思想。在构造函数中，先预处理计算出数组 nums 的前缀和数组 presum，其中 presum[i] 表示 nums[0] 到 nums[i-1] 的累加和。在 sumRange 查询函数中，利用前缀和数组快速计算出区间 [left, right] 的累加和，只需要用 presum[right+1] 减去 presum[left] 即可得到结果。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

为什么在前缀和数组`presum`中，索引0的值被初始化为0，这样的设计有什么特别的用处吗？

▷

在前缀和数组`presum`中，索引0的值被初始化为0，这主要是为了方便计算从数组开头到某一位置的累加和。具体来说，当需要计算从`nums[0]`到`nums[right]`的累加和时，直接使用`presum[right+1]`即可得到结果。这种设计避免了在计算区间和时需要进行特殊判断或额外的计算来处理从数组开头开始的累加情况。

🦆

在构造`NumArray`类时，计算前缀和数组`presum`的循环中，`presum[i] = presum[i-1] + nums[i-1]`这一步是如何确保数组索引不会越界的？

▷

在构造`NumArray`类时，创建的前缀和数组`presum`长度为`n+1`，其中`n`是输入数组`nums`的长度。因此在循环计算前缀和时，`presum[i]`的索引从1开始，最大到`n`，对应的`nums[i-1]`的索引从0开始，最大到`n-1`。这样设计保证了访问`nums[i-1]`时，索引始终在有效范围内，不会越界。

🦆

在方法`sumRange`中，直接使用`presum[right+1] - presum[left]`来获取区间和的原理是什么？能否详细解释这种计算方式的数学依据？

▷

方法`sumRange`使用`presum[right+1] - presum[left]`来计算区间[left, right]的和的原理基于前缀和的定义。`presum[i]`表示从`nums[0]`到`nums[i-1]`的累加和。因此，`presum[right+1]`表示从`nums[0]`到`nums[right]`的累加和，而`presum[left]`表示从`nums[0]`到`nums[left-1]`的累加和。从`presum[right+1]`中减去`presum[left]`，就剔除了`nums[0]`到`nums[left-1]`的部分，恰好得到从`nums[left]`到`nums[right]`的累加和。

🦆

如果输入的索引`left`或`right`不在数组`nums`的有效范围内，`sumRange`方法会如何处理？是否有错误处理机制？

▷

题解中的`sumRange`方法并没有直接提到对索引`left`或`right`超出数组有效范围的处理机制。在实际应用中，应当在方法调用前或方法内部添加索引合法性的检查，例如确保`0 <= left <= right < nums.length`。如果不进行这样的检查，试图访问超出范围的前缀和数组`presum`的元素可能导致运行时错误。

相关问题

二维区域和检索 - 矩阵不可变

给定一个二维矩阵 matrix，以下类型的多个请求：

计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。

实现 NumMatrix 类：

NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素总和。

示例 1：

输入: 
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出: 
[null, 8, 11, 12]

解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

提示：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
-10⁵ <= matrix[i][j] <= 10⁵
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
最多调用 10⁴ 次 sumRegion 方法

区域和检索 - 数组可修改

给你一个数组 nums ，请你完成两类查询。

其中一类查询要求更新数组 nums 下标对应的值
另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（包含）的nums元素的和，其中 left <= right

实现 NumArray 类：

NumArray(int[] nums) 用整数数组 nums 初始化对象
void update(int index, int val) 将 nums[index] 的值更新为 val
int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（包含）的nums元素的和（即，nums[left] + nums[left + 1], ..., nums[right]）

示例 1：

输入：
["NumArray", "sumRange", "update", "sumRange"]
[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
输出：
[null, 9, null, 8]

解释：
NumArray numArray = new NumArray([1, 3, 5]);
numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9
numArray.update(1, 2);   // nums = [1,2,5]
numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8

提示：

1 <= nums.length <= 3 * 10⁴
-100 <= nums[i] <= 100
0 <= index < nums.length
-100 <= val <= 100
0 <= left <= right < nums.length
调用 update 和 sumRange 方法次数不大于 3 * 10⁴

和等于 k 的最长子数组长度

包含全部黑色像素的最小矩形二维区域和检索 - 矩阵不可变