本文首发自本人微信公众号：今天你A了吗。每日算法讲解，面试题，冲刺BAT大厂。微信扫码关注吧：
前缀和（一）仅涉及一维前缀和。前缀和（二）涉及二维前缀和。
一、介绍：什么是前缀和假设我们有一个字符串ABCDE，什么是这个单词的前缀，A、AB、ABC、ABCD、ABCDE就是这个单词的前缀，就是从第一个字母开始，依次往后拼接。E、ED、EDC、EDCB、EDCBA被称为这个单词的后缀。
那么对于一个数组的前缀，例如数组a = [1,2,3,4,5]，我们维护一个由前缀的和组成的数组sum，sum[i]表示数组中a[0]~ a[i] 的和。
sum[0] = a[0]
sum[1] = a[0] + a[1]
sum[2] = a[0] + a[1] + a[2]
sum[3] = a[0] + a[1] + a[2] + a[3]
sum[4] = a[0] + a[1] + a[2] + a[3] + a[4]
sum数组就被称为前缀和数组。
前缀和的最主要目的就是求子数组的和的大小。例如元素a[1]到a[3]的和。
a[1] + a[2] + a[3] = sum[3] - sum[0]
注意：这里sum中的i表示的是前i个数的和，不是下标，因为题目中需要用到前0个数的和。
下面通过一个例子说明一下前缀和的作用。
LeetCode 560.和为k的子数组：https://leetcode-cn.com/problems/subarray-sum-equals-k/
题意：给定一个整数数组和一个整数 k你需要找到该数组中和为 k的连续的子数组的个数。
思路1： 如果只使用for循环枚举子数组，并且求和，时间复杂度为O(n3)使用前缀和。使用前缀和：每次求出子数组的和，与k进行比较，时间复杂度O(n2)。
class Solution { public int subarraySum(int[] nums, int k) { int n = nums.length; int count = 0; int[] sum = new int[n]; //前缀和数组 //得到前缀和数组 sum[0] = nums[0]; for(int i = 1; i < n; i++){ sum[i] = sum[i-1] + nums[i]; } //列举子数组 for(int i = 0; i < n; i++){ for(int j = -1; j < i; j++){ //这里从-1开始下面有解释 int sumOfSub; if(j < 0) sumOfSub = sum[i]; else sumOfSub = sum[i] - sum[j]; if(sumOfSub == k) count++; } } return count; }}解释：关于题目中的j = -1
a[1]+a[2] = sum[2]-sum[0]
a[0]+a[1]+a[2] = sum[2] //这里不需要减去任何东西，所以代码中用一个-1来表示这种特殊情况。
思路二: 使用Map + 前缀和进行优化
在上一个思路中，我们要求一个结尾下标为i的子数组的和是否为k，就需要对j从-1遍历到i-1，来找到是存在否sum[i] - k = sum[j]。那么我们只要用map<前i个元素的前缀和，出现的次数>把i之前的前缀和的值记录下来，判断map中是否包含sum[i] - k即可。时间复杂度O(n)