本文首发自本人微信公众号：今天你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(n³)使用前缀和。使用前缀和：每次求出子数组的和，与k进行比较，时间复杂度O(n²)。

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];elsesumOfSub = 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)

class Solution {public int subarraySum(int[] nums, int k) {int n = nums.length;int count = 0;int[] sum = new int[n]; //前缀和数组Map<Integer, Integer> map = new HashMap<>();map.put(0, 1); //放入没有前缀和这种特殊情况，见思路一的解释，0这个值出现了1次//得到前缀和数组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++){if(map.containsKey(sum[i]-k))count += map.get(sum[i]-k) ;map.put(sum[i], map.getOrDefault(sum[i], 0) + 1);}return count;}
}

四、相关题目

1365. 有多少小于当前数字的数字 https://leetcode-cn.com/problems/how-many-numbers-are-smaller-than-the-current-number/
1366. 统计「优美子数组」 https://leetcode-cn.com/problems/count-number-of-nice-subarrays/