题目描述
这是 LeetCode 上的 303. 区域和检索 - 数组不可变 ，难度为 简单。
Tag : 「前缀和」、「区间求和问题」
给定一个整数数组 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^4104
- -10^5105 <= nums[i] <= 10^5105
- 0 <= i <= j < nums.length
- 最多调用 $10^4# 次 sumRange 方法
前缀和解法（一维）
这是一道前缀和的裸题。
当需要我们求「某一段」区域的和的时候，我们要很自然的想到「前缀和」。
前缀和的作用就是为了帮助我们快速求某一段的和，是「差分」的逆运算。
前缀和数组 sum 的每一位记录的是当前位置距离起点位置，这连续一段的和区间和。
因此当我们要求特定的一段 [i,j] 的区域和的时候，可以直接利用前缀和数组快速求解：ans = sum[j] - sum[i - 1]。
由于涉及 -1 操作，为了减少一些边界处理，我们可以使前缀和数组下标从 1 开始记录，然后在进行答案计算的时候，根据源数组下标是否从 1 开始决定是否产生相应的偏移：
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]; } } 复制代码
- 时间复杂度：预处理前缀和数组需要对原数组进行线性扫描，复杂度为 O(n)O(n)，计算结果复杂度为 O(1)O(1)。整体复杂度为 O(n)O(n)
- 空间复杂度：O(n)O(n)
一维前缀和模板
我们再来整理下一维「前缀和」的模板代码：
// 预处理前缀和数组 { 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 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
