前言
就从数组开始，当前会始终更新算法。数组有下图这些知识点与技巧。本文次要解说其中的前缀和知识点。
思路
适宜的场景：原始数组不会被批改，且频繁查问某个区间的累加和。
创立一个prefixSum数组，长度比原数组nums长度多1。prefixSum[i]存储nums[0]到nums[i]的和。
尤其要留神prefixSum与nums的坐标换算，如下图所示。
区域和检索 - 数组不可变（一维前缀和）
leetcode第303题
解题思路
惯例思路是通过遍历i到j。但这样工夫复杂度就是O(n)。
采纳前缀和。sumRange = prefixSum[right + 1] - prefixSum[left]。留神原数组与前缀和数组的下标换算，例如nums[i]的前缀和是preSum[i + 1]。如下图所示。
复杂度剖析
工夫复杂度：初始化O(n)，每次检索O(1)，n是数组长度。
空间复杂度：O(n)。
代码
class NumArray { private int[] prefixSum; public NumArray(int[] nums) { prefixSum = new int[nums.length + 1]; for (int i = 0; i < nums.length; i++) { prefixSum[i + 1] = prefixSum[i] + nums[i]; } } public int sumRange(int left, int right) { return prefixSum[right + 1] - prefixSum[left]; }}
二维区域和检索 - 矩阵不可变（二维前缀和）
leetcode第304题
解题思路
题中要求值设为下图中的红框局部，则有下图红框局部和 = 下图蓝框局部的和 - 下图绿框局部的和 - 下图黄框局部的和 + 下图灰框局部的和。
定义原二维数组的前缀和数组为preSum。则preSumi示意原数组中(0, 0)坐标与(i - 1, j - 1)坐标组成的矩形区域的和，如下图所示，紫色框对应的前缀和为17。
这里须要留神原数组与前缀和数组的坐标换算。比方原数组坐标为(i - 1, j - 1)，则在前缀和数组中的坐标为(i, j)。
而下面一开始提到的蓝框的和，绿框的和，黄框的和，灰框的和的求法都一样。也就是对应地位二维数组的前缀和。
所以上图中紫色局部前缀和又如何求呢？答案：上图紫色局部前缀和 = 下图黄色局部前缀和 + 下图红色局部前缀和 - 重叠局部前缀和 + 原数组(i - 1, j - 1)地位的值 ，即preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1] = 9 + 14 - 8 + 2 = 17。
所以只要求出原数组中每个地位的前缀和，就解决了本题。
复杂度剖析
工夫复杂度：初始化O(rc)，每次检索O(1)，其中r与c别离为matrix的行数和列数。
空间复杂度：O(rc)。
代码
class NumMatrix { private int[][] preSum; public NumMatrix(int[][] matrix) { int r = matrix.length; if (r == 0) { return; } int c = matrix[0].length; if (c == 0) { return; } preSum = new int[r + 1][c + 1]; for (int i = 1; i <= r; i++) { for (int j = 1; j <= c; j++) { preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1]; } } } public int sumRegion(int row1, int col1, int row2, int col2) { return preSum[row2 + 1][col2 + 1] - preSum[row1][col2 + 1] - preSum[row2 + 1][col1] + preSum[row1][col1]; }}
和为 K 的子数组
leetcode第560题
解题思路
思路
惯例思路是通过双重循环遍历前缀和数组，j < i，若当preSum[j] + k == preSum[i]时，阐明数组从j - 1到i的和为k，则count++。但这样工夫复杂度就是O(n^2)。
采纳HashMap + 前缀和数组形式，工夫复杂度可达到O(n)。
由preSum[j] + k == preSum[i]移项得preSum[j] == preSum[i] - k。所以只有统计有多少个前缀和为preSum[i] - k即能够统计出有多少个子串的和为k。
建设map，其中key=preSum[i]，value=满足preSum[i] - k的preSum[j]有多少个（有多少个满足，就代表有多少个子串的和为k），其中必须j < i。
示例
示例nums = [1,2,3]，k = 3。流程如下。
1.因为不会当时构建前缀和数组，所以此处先增加前缀和的第0个元素。如下图所示。
2.从nums的第0项（对应前缀和数组的第1项），开始遍历。此时preSum - k = -2。map中不存在key = -2的键值对。所以此时count = 0。并将key = preSum = 1， value = 1退出map。如下图所示。
3.拜访nums数组的第1项（对应前缀和数组的第2项）。此时preSum - k = 0。map中存在key =0的键值对，且value = 1。所以此时count = count + value = 1。并将key = preSum = 3， value = 1退出map。如下图所示。
4.拜访nums数组的第2项（对应前缀和数组的第3项）。此时preSum - k = 3。map中存在key = 3的键值对，且value = 1。所以此时count = count + value = 2。并将key = preSum = 6， value = 1退出map。如下图所示。
复杂度剖析
工夫复杂度：O(n)，其中n为数组的长度
空间复杂度：O(n)，哈希表在最坏状况下可能有n个不同的键值，因而为O(n)。
代码
class Solution { public int subarraySum3(int[] nums, int k) { HashMap<Integer, Integer> map = new HashMap<>(); //初始状况，因为此处没有应用前缀和数组，因而须要先将前缀和为0的，呈现了1次的的状况记录在map外面，也就是前缀数组中的第0项 map.put(0, 1); int count = 0, sum0i = 0; for (int i = 0; i < nums.length; i++) { sum0i += nums[i]; count += map.getOrDefault(sum0i - k, 0); //以下两句代码，必须在以上两句代码的后边，这样变相保障了j < i int c = map.getOrDefault(sum0i, 0); map.put(sum0i, ++c); } return count; }}
结尾
好了数组中的前缀和技巧就讲这三道。下一篇算法文章讲差分数组。
微信扫描下方二维码，关注公众号后回复【笔记】，有我筹备的15万字Java面试笔记。
感激各位人才的点赞、珍藏和评论，干货文章继续更新中，下篇文章再见！