前缀和是一种重要的预处理，能大大降低查询的时间复杂度。
【一维前缀和】
给定一个数组A[1,2,……n]，则它的前缀和数组为PrefixSum[1..n]。定义为：PrefixSum[i] = A[0]+A[1]+...+A[i-1]；
【例子】
A[5,6,7,8] --> PrefixSum[5,11,18,26]
PrefixSum[0] =A[0] ;
PrefixSum[1] =A[0] + A[1] ;
PrefixSum[2] =A[0] + A[1] + A[2] ;
PrefixSum[3] =A[0] + A[1] + A[2] + A[3] ;
【用法】
- 可以通过前缀和求出任意区间的求和值，比如我们想求出[5,10]区间内的求和值，即s[10]-s[4]=[5,10]
【思路】
对于一个给定的数组nums，使用额外开辟一个前缀和数组preSum进行预处理：
int n = nums.length;
// 前缀和数组
int[] preSum = new int[n + 1];
preSum[0] = 0;
for (int i = 0; i < n; i++)preSum[i + 1] = preSum[i] + nums[i];通过前缀和，想要求nums[i...j]的和，只需要一步操作：preSum[j+1] - preSum[i]即可。
【题目 Leetcode 560】
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
思路1：前缀和
int subarraySum(int[] nums, int k) {int n = nums.length;// 构造前缀和int[] sum = new int[n + 1];sum[0] = 0; for (int i = 0; i < n; i++)sum[i + 1] = sum[i] + nums[i];int ans = 0;// 穷举所有子数组for (int i = 1; i <= n; i++)for (int j = 0; j < i; j++)// sum of nums[j..i-1]if (sum[i] - sum[j] == k)ans++;return ans;
}时间复杂度：O(N*N)
空间复杂度：O(N)
对于这个前缀和方法来说，时间复杂度过于大了。
优化：
主要是时间复杂度消耗在两个for循环中，在计算有几个 j 能够使得 sum[i] 和 sum[j] 的差为 k。毎找到一个这样的 j，就把结果加一。
那么，如果直接记录下有几个sum[j]和sum[i] - k相等，直接更新结果，就避免了内层的for循环。
这里就用到了hash表。
代码如下：
public int subarraySum(int[] nums, int k) {int length = nums.length;Map<Integer,Integer> presum = new HashMap<>();presum.put(0,1);int ans = 0;int sum_i = 0;for(int i = 0; i < length; i++){sum_i += nums[i];int sum_j = sum_i - k;if(presum.containsKey(sum_j)){ans += presum.get(sum_j);}presum.put(sum_i, presum.getOrDefault(sum_i, 0) + 1);}return ans;}对于hash表的用法，在另一章中讲解。
那么在这里时间复杂度就成了O(N)了。
【二维前缀和】
从上图中可以看出，前缀和数组里每一个位置都表示原数组当前index左上方的数字的和。
比如像图里面画的：prefixSum[3, 3] = src[0~2, 0~2]的和;
二维前缀和数组要怎么计算出来呢？
可以分为四种情况
- i==0 && j==0，只有一个直接赋值即可：prefixSum[0, 0] = src[0, 0]。
- i==0，最左边的一排，图中黄色部分，prefixSum[0, j] = prefixSum[0, j-1] + src[0, j]；
- j==0，最上面一排，途中红色部分，prefixSum[i, o] = prefixSum[i-1, 0] + src[i, 0];
- i!=0 || j!=0，图中绿色部分，prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] + src[i][j] - prefixSum[i - 1][j - 1];
我们要得到prefixSum[2,2]，我们知道应该是图一中箭头指向的区域。也就是9个方框加起来的和，也就是54。
看图二，我们可以利用prefixSum[1, 2]和prefixSum[2, 1]，但是他俩的区域是重合的，如图二所示，重合的区域又恰好是prefixSum[1, 1]负责的区域，相当于加了两份，需要减掉一份。
所以prefixSum[2,2] = prefixSum[1, 2] + prefixSum[2, 1] - prefixSum[1, 1] + src[2, 2];
也就是54 = 33 + 21 -12(这个是prefixSum[1, 1]) +12(这是src[2, 2])
for (int i = 0; i < src.length; i++) {for (int j = 0; j < src[0].length; j++) {if (i == 0 && j == 0) {//第0个，最左上角result[i][j] = src[i][j]} else if (i == 0) {//第一行，最顶部一行result[i][j] = result[i][j - 1] + src[i][j]} else if (j == 0) {//第一列，最左边一列result[i][j] = result[i - 1][j] + src[i][j]} else {//其他result[i][j] = result[i - 1][j] + result[i][j - 1] + src[i][j] - result[i - 1][j - 1]}}}return result;
