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

题目描述

这是 LeetCode 上的 303. 区域和检索 - 数组不可变 ，难度为 简单。

给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。

实现 NumArray 类：

• NumArray(int[] nums) 使用数组 nums 初始化对象
• int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）

示例：

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

提示：

• $0 <= nums.length <= 10^4$
• $-10^5 <= nums[i] <= 10^5$
• $0 <= i <= j < nums.length$
• 最多调用 $10^4$ 次 sumRange 方法

---

前缀和（一维）

这是一道前缀和裸题。

当要我们求「连续段」区域和的时候，要很自然的想到「前缀和」。

所谓前缀和，是指对原数组“累计和”的描述，通常是指一个与原数组等长的数组。

设前缀和数组为 sum，sum 的每一位记录的是从「起始位置」到「当前位置」的元素和。例如 $sum[x]$ 是指原数组中“起始位置”到“位置 x”这一连续段的元素和。

有了前缀和数组 sum，当我们求连续段 $[i, j]$ 的区域和时，利用「容斥原理」，便可进行快速求解。

通用公式：ans = sum[j] - sum[i - 1]。

由于涉及 -1 操作，为减少边界处理，我们可让前缀和数组下标从 $1$ 开始。在进行快速求和时，再根据原数组下标是否从 $1$ 开始，决定是否进行相应的下标偏移。

Java 代码：

class NumArray {
    int[] sum;
    public NumArray(int[] nums) {
        int n = nums.length;
        // 前缀和数组下标从 1 开始，因此设定长度为 n + 1（模板部分）
        sum = new int[n + 1];
        // 预处理除前缀和数组（模板部分）
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
    }
    public int sumRange(int i, int j) {
        // 求某一段区域和 [i, j] 的模板是 sum[j] - sum[i - 1]（模板部分）
        // 但由于我们源数组下标从 0 开始，因此要在模板的基础上进行 + 1
        i++; j++;
        return sum[j] - sum[i - 1];
    }
}

C++ 代码：

class NumArray {
public:
    vector<int> sum;
    NumArray(std::vector<int>& nums) {
        int n = nums.size();
        // 前缀和数组下标从 1 开始，因此设定长度为 n + 1（模板部分）
        sum.resize(n + 1, 0);
        // 预处理除前缀和数组（模板部分）
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
    }
    int sumRange(int i, int j) {
        // 求某一段区域和 [i, j] 的模板是 sum[j] - sum[i - 1]（模板部分）
        // 但由于我们源数组下标从 0 开始，因此要在模板的基础上进行 + 1
        i++; j++;
        return sum[j] - sum[i - 1];
    }
};

Python 代码：

class NumArray:
    def __init__(self, nums: List[int]):
        n = len(nums)
        # 前缀和数组下标从 1 开始，因此设定长度为 n + 1（模板部分）
        self.sum = [0] * (n + 1)
        # 预处理除前缀和数组（模板部分）
        for i in range(1, n + 1):
            self.sum[i] = self.sum[i - 1] + nums[i - 1]

    def sumRange(self, i: int, j: int) -> int:
        # 求某一段区域和 [i, j] 的模板是 sum[j] - sum[i - 1]（模板部分）
        # 但由于我们源数组下标从 0 开始，因此要在模板的基础上进行 + 1
        i, j = i + 1, j + 1
        return self.sum[j] - self.sum[i - 1]

TypeScript 代码：

class NumArray {
    private sum: number[];
    constructor(nums: number[]) {
        const n: number = nums.length;
        // 前缀和数组下标从 1 开始，因此设定长度为 n + 1（模板部分）
        this.sum = new Array(n + 1).fill(0);
        // 预处理除前缀和数组（模板部分）
        for (let i = 1; i <= n; i++) this.sum[i] = this.sum[i - 1] + nums[i - 1];
    }
    sumRange(i: number, j: number): number {
        // 求某一段区域和 [i, j] 的模板是 sum[j] - sum[i - 1]（模板部分）
        // 但由于我们源数组下标从 0 开始，因此要在模板的基础上进行 + 1
        i++; j++;
        return this.sum[j] - this.sum[i - 1];
    }
}

• 时间复杂度：预处理前缀和数组需要对原数组进行线性扫描，复杂度为 $O(n)$，计算结果复杂度为 $O(1)$。整体复杂度为 $O(n)$
• 空间复杂度：$O(n)$

---

一维前缀和模板

我们再来整理下一维「前缀和」的模板代码（Java 为例）：

// 预处理前缀和数组
{    
    sum = new int[n + 1];
    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + nums[i - 1];
}

// 计算 [i, j] 结果
{
    i++; j++;
    ans = sum[j] - sum[i - 1];
}

---

总结

最后我们看看「前缀和」与其他知识点的联系。

为啥「前缀和」能大幅度的降低区间求和的复杂度？其实本质是利用数学进行求值：某一段的区间和 = 起点到区间右端点的和（含右端点）- 起点到区间左端点的和（不含左端点）

而求解前缀和数组的过程，则是基于动态规划思想：由于前缀和的每一位都是求「当前位置到起点位置区间的和」。因此当求解某一位的前缀和时，需要「前一位置的前缀和」和「当前位置的原数组值」（而与前一位置的前缀和是如何计算出来无关）。其过程类似于 dp 入门题 509. 斐波那契数 的求解过程。

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.303 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。