LeetCode题练习与总结：区域和检索 - 数组不可变--303

一、题目描述

给定一个整数数组  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 <= 10^4
• -10^5 <= nums[i] <= 10^5
• 0 <= i <= j < nums.length
• 最多调用 10^4 次 sumRange 方法

二、解题思路

为了高效地处理多次范围求和的查询，我们可以使用前缀和的技术。前缀和是一种预处理技术，可以在常数时间内返回任意子数组的和。

具体步骤如下：

1. 在构造函数 NumArray(int[] nums) 中，首先计算并存储数组 nums 的前缀和。前缀和数组 prefixSums 的第 i 个元素表示从 nums[0] 到 nums[i-1] 的和。
2. 在 sumRange(int left, int right) 方法中，利用前缀和数组快速计算任意 left 到 right 范围的和。如果 left 是 0，那么返回 prefixSums[right + 1]，否则返回 prefixSums[right + 1] - prefixSums[left]。

三、具体代码

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

四、时间复杂度和空间复杂度

1. 时间复杂度

• 构造函数 NumArray(int[] nums):

  • 构造函数中有一个循环，该循环遍历输入数组 nums 一次。
  • 在每次循环中，执行的是常数时间的操作（即一次加法和一次赋值）。
  • 因此，构造函数的时间复杂度是 O(n)，其中 n 是数组 nums 的长度。

• 方法 sumRange(int left, int right):

  • sumRange 方法中只有一次减法操作，它涉及对前缀和数组 prefixSums 的两次访问。
  • 由于数组访问的时间复杂度是 O(1)，所以 sumRange 方法的时间复杂度也是 O(1)。

2. 空间复杂度

• 构造函数 NumArray(int[] nums):

  • 构造函数中创建了一个新的数组 prefixSums，其大小是输入数组 nums 的长度加 1。
  • 因此，构造函数的空间复杂度是 O(n)，其中 n 是数组 nums 的长度。

• 方法 sumRange(int left, int right):

  • sumRange 方法没有使用额外的空间（除了输入参数和返回值）。
  • 因此，sumRange 方法的空间复杂度是 O(1)。

五、总结知识点

1. 类定义:class NumArray 定义了一个名为 NumArray 的类，这是面向对象编程的基本概念。

2. 成员变量:private int[] prefixSums; 声明了一个私有成员变量 prefixSums，用于存储前缀和数组。私有成员变量意味着它只能在类的内部被访问。

3. 构造函数:public NumArray(int[] nums) 定义了类的构造函数，用于初始化对象时执行。构造函数接受一个整数数组 nums 作为参数。

4. 数组操作:在构造函数中，通过循环初始化 prefixSums 数组，展示了数组的创建和索引访问。

5. 前缀和算法:前缀和是一种算法，用于快速计算数组任意子数组的和。它通过累加前 i 个元素来构建前缀和数组。

6. 方法定义:public int sumRange(int left, int right) 定义了一个公共方法 sumRange，用于计算并返回从索引 left 到 right 的子数组的和。

7. 方法调用:在 sumRange 方法中，通过 prefixSums[right + 1] - prefixSums[left] 来计算子数组的和，这是前缀和算法的核心。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。