前缀和实现题目：区域和检索 - 数组不可变

题目

标题和出处

标题：区域和检索 - 数组不可变

出处：303. 区域和检索 - 数组不可变

难度

3 级

题目描述

要求

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

• 计算下标 $\text{left}$ 和 $\text{right}$ 之间的 $\text{nums}$ 元素的和（包含 $\text{left}$ 和 $\text{right}$），其中 $\text{left}\le \text{right}$。

实现 $\text{NumArray}$ 类：

• $\text{NumArray(int[] nums)}$ 使用数组 $\text{nums}$ 初始化对象。
• $\text{int sumRange(int left, int right)}$ 返回数组 $\text{nums}$ 中的下标 $\text{left}$ 和 $\text{right}$ 之间的元素的和，包含 $\text{left}$ 和 $\text{right}$（即 $\text{nums[left] + nums[left + 1] + ... + nums[right]}$）。

示例

示例 1：

输入：
$\text{["NumArray", "sumRange", "sumRange", "sumRange"]}$
$\text{[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]}$
输出：
$\text{[null, 1, -1, -3]}$
解释：
$\text{NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);}$
$\text{numArray.sumRange(0, 2);}$ // 返回 $\text{(-2) + 0 + 3 = 1}$
$\text{numArray.sumRange(2, 5);}$ // 返回 $\text{3 + (-5) + 2 + (-1) = -1}$
$\text{numArray.sumRange(0, 5);}$ // 返回 $\text{(-2) + 0 + 3 + (-5) + 2 + (-1) = -3}$

数据范围

• $\text{1}\le \text{nums.length}\le {\text{10}}^{\text{4}}$
• ${\text{-10}}^{\text{5}}\le \text{nums[i]}\le {\text{10}}^{\text{5}}$
• $\text{0}\le \text{left}\le \text{right}<\text{nums.length}$
• 最多调用 ${\text{10}}^{\text{4}}$ 次 $\text{sumRange}$

解法

思路和算法

这道题是一维前缀和的实现与应用。计算数组 $\text{nums}$ 中的任意子数组的元素和，方法是首先计算数组 $\text{nums}$ 的前缀和数组，然后根据前缀和数组在 $O(1)$ 的时间内计算任意子数组的元素和。

用 $n$ 表示数组 $\text{nums}$ 的长度，创建长度为 $n+1$ 的前缀和数组 $\text{prefixSums}$，对于 $0\le i\le n$，$\text{prefixSums}[i]$ 表示 $\text{nums}$ 的长度为 $i$ 的前缀和，即下标范围 $[0,i-1]$ 中的 $i$ 个元素之和：

$$\text{prefixSums}[i]=\sum _{k=0}^{i-1}\text{nums}[k]$$

特别地，$\text{prefixSums}[0]=0$。

对于 $0\le i<n$，考虑 $\text{prefixSums}[i+1]$ 与 $\text{prefixSums}[i]$ 之差：

$$\begin{array}{rl}& \text{prefixSums}[i+1]-\text{prefixSums}[i]\\ =& \sum _{k=0}^i\text{nums}[k]-\sum _{k=0}^{i-1}\text{nums}[k]\\ =& \sum _{k=0}^{i-1}\text{nums}[k]+\text{nums}[i]-\sum _{k=0}^{i-1}\text{nums}[k]\\ =& \text{nums}[i]\end{array}$$

因此 $\text{prefixSums}[i+1]-\text{prefixSums}[i]=\text{nums}[i]$，$\text{prefixSums}[i+1]=\text{prefixSums}[i]+\text{nums}[i]$。当 $\text{prefixSums}[i]$ 的值已知时，可以使用 $O(1)$ 的时间计算 $\text{prefixSums}[i+1]$ 的值，因此可以使用 $O(n)$ 的时间计算整个前缀和数组。

得到前缀和数组 $\text{prefixSums}$ 之后，对于 $0\le \text{left}\le \text{right}<n$，下标范围 $[\text{left},\text{right}]$ 的子数组的元素和可以通过前缀和数组得到：

$$\text{sumRange}(\text{left},\text{right})=\text{prefixSums}[\text{right}+1]-\text{prefixSums}[\text{left}]$$

代码

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

复杂度分析

• 时间复杂度：构造方法的时间复杂度是 $O(n)$，$\text{sumRange}$ 操作的时间复杂度是 $O(1)$，其中 $n$ 是数组 $\text{nums}$ 的长度。构造方法需要创建长度为 $n+1$ 的前缀和数组并计算每个元素的前缀和，每次 $\text{sumRange}$ 操作计算子数组的元素和的时间是 $O(1)$。

• 空间复杂度：$O(n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。需要创建长度为 $n+1$ 的前缀和数组。