前缀和数组
# 前缀和数组
相关习题：
303. 区域和检索 - 数组不可变（中等） (opens new window)
304. 二维区域和检索 - 矩阵不可变（中等） (opens new window)
560. 和为K的子数组（中等） (opens new window)
# 区域和检索-数组不可变
题目：
给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j两点。
思路：
因为题目已经给出了我们的索引i 到 j（i ≤ j），故我们容易想到直接把指定索引下标的数组元素加起来就可以了，得到如下代码：
class NumArray {
private int[] myArray;
public NumArray(int[] nums) {
this.myArray = nums;
}
public int sumRange(int left, int right) {
int sum = 0;
for (int i = left; i <= right; i++) {
sum += myArray[i];
}
return sum;
}
}
这样，可以达到效果，但是效率很差，因为 sumRange ⽅法会被频繁调⽤，⽽它的时间复杂度是 O(N)，其 中 N 代表 nums 数组的⻓度。
现在我们来采用前缀和的技巧，将 sumRange 函数的时间复杂度降为 O(1)，说⽩了就是不要在 sumRange ⾥⾯⽤ for 循环。
代码：
class NumArray {
private int[] myArray;
public NumArray(int[] nums) {
myArray = new int[nums.length + 1];
myArray[0] = 0;
for (int i = 1; i < myArray.length; i++) {
myArray[i] = myArray[i - 1] + nums [i -1];
}
}
public int sumRange(int left, int right) {
return myArray[right + 1] - myArray[left];
}
}
# 二维区域和检索 - 矩阵不可变
题目：
给定一个二维矩阵 matrix，以下类型的多个请求：
计算其子矩形范围内元素的总和，该子矩阵的 左上角 为 (row1, col1) ，右下角 为 (row2, col2) 。 实现 NumMatrix 类：
NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化 int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素 总和 。
思路：
采用的方法还是前缀和，但是这个前缀和是某一个点到原点的矩阵之和。
代码：
class NumMatrix {
private int [][] sum;
public NumMatrix(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
sum = new int[m+1][n+1];
for (int i = 1; i < sum.length; i++) {
for (int j = 1; j < sum[0].length; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + matrix[i - 1][j - 1] - sum[i - 1][j - 1];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
return sum[row2 + 1][col2 + 1] + sum[row1][col1] - sum[row1][col2 + 1] - sum[row2 + 1][col1];
}
}
# 和为 K 的子数组
题目：
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。
思路：
前缀和是从1到n连续的，现在这个子数组，可以是从i到j的之和。但是i到j的之和可以演变成j的前缀和减去i的前缀和。故只需要用两个for循环，去得到对应i到j的之和为k的个数即可。
代码：
class Solution {
public int subarraySum(int[] nums, int k) {
int[] poArray = new int[nums.length + 1];
poArray[0] = 0;
for (int i = 1; i < poArray.length; i++) {
poArray[i] = poArray[i - 1] + nums[i -1];
}
int result = 0;
for (int i = 0; i < poArray.length; i++) {
for (int j = i + 1; j < poArray.length; j++) {
if (poArray[j] - poArray[i] == k) {
result++;
}
}
}
return result;
}
}
但是现在这个这个解法的时间复杂度 O(N^2) 空间复杂度 O(N)，并不是最优的解法。不过通过这个解法理解了前缀和数组的⼯作原理之后，可以使⽤⼀些巧妙的办法把时间复杂度进⼀步降低。
看到一些使用前缀和和哈希表结合的方式，首先我们来看看我们之前写的代码核心部分：
for (int i = 0; i < poArray.length; i++) {
for (int j = i + 1; j < poArray.length; j++) {
if (poArray[j] - poArray[i] == k) {
result++;
}
}
}
我们的第二层for循环所作的主要事情就是有⼏个 j 能够使得 poArray[j] 和 poArray[i] 的差为 k。毎找到⼀个这样的 j，就把结果加⼀。
对这个if语句进行优化：
if(poArray[i] == poArray[j] - k)
result++;
所以我们只需要算出poArray[i]出现的次数即可，而这个poArray[i]是我们的前缀和减去k。
class Solution {
public int subarraySum(int[] nums, int k) {
HashMap<Integer, Integer> preSum = new HashMap<>();
// 前缀和为0，出现次数为1
preSum.put(0, 1);
int result = 0;
int iSum = 0;
for (int num : nums) {
iSum += num;
if (preSum.containsKey(iSum - k)) {
result += preSum.get(iSum - k);
}
preSum.put(iSum, preSum.getOrDefault(iSum, 0) + 1);
}
return result;
}
}
# 前缀和总结
前缀和主要适⽤的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。
核心代码：
class PrefixSum {
// 前缀和数组
private int[] prefix;
/* 输⼊⼀个数组，构造前缀和 */
public PrefixSum(int[] nums) {
prefix = new int[nums.length + 1];
// 计算 nums 的累加和
for (int i = 1; i < prefix.length; i++) {
prefix[i] = prefix[i - 1] + nums[i - 1];
}
}
/* 查询闭区间 [i, j] 的累加和 */
public int query(int i, int j) {
return prefix[j + 1] - prefix[i];
}
}
# 参考
小而美的算法技巧：前缀和数组 (opens new window)
https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/bao-li-jie-fa-qian-zhui-he-qian-zhui-he-you-hua-ja/