Leetcode---8.前缀和篇
前缀和指一个数组的某下标之前的所有数组元素的和（包含其自身），前缀和是一种重要的预处理，能够降低算法的时间复杂度。
preSum是前缀和数组, nums是内容数组。
拥有前缀和数组后, 我们可以在O(1)的时间复杂度内求出区间和。
点击查看代码
class NumArray {
// 前缀和数组
private int[] preSum;
/* 输入一个数组，构造前缀和 */
public NumArray(int[] nums) {
// preSum[0] = 0，便于计算累加和
preSum = new int[nums.length + 1];
// 计算 nums 的累加和
for (int i = 1; i < preSum.length; i++) {
preSum[i] = preSum[i - 1] + nums[i - 1];
}
}
/* 查询闭区间 [left, right] 的累加和 */
public int sumRange(int left, int right) {
return preSum[right + 1] - preSum[left];
}
}
new 一个新的数组 preSum 出来，preSum[i] 记录 nums[0..i-1] 的累加和。如果我想求索引区间 [1, 4] 内的所有元素之和，就可以通过 preSum[5] - preSum[1] 得出。这样，sumRange 函数仅仅需要做一次减法运算，避免了每次进行 for 循环调用，最坏时间复杂度为常数 O(1)。
参考链接：
【1】得嘞,一文把前缀和给扒的干干净净
【2】小而美的算法技巧：前缀和数组