算法技巧-前缀和
前缀和算法技巧是一种常用的算法技巧，用于快速计算数组或序列的前缀和。
1. 技巧说明
前缀和算法，是用来快速求解数组中某一个区间的区间和的值，如果对于每一个询问，都可以在O(1)的时间复杂度内快速求解，如果使用枚举的思想，则平均复杂度为O(n)，远高于O(1)的复杂度。
那么前缀和是如何做到这一点的，其实是通过区间拆分+预处理的思想得到的，预处理的复杂度为O(n)。
1.1 算法步骤
对于给定的一个数组，如下图所示，其中，0~8为数组的下标
那么，对于数组任意的一个区间范围[i,j]，如何快速地求解它的区间和？ 首先，我们可以看几个例子
[0,2]的区间和为w[0]+w[1]+w[2]=1+2+4=7
[1,3]的区间和为w[1]+w[2]+w[3]=2+4+5=11
我们可以预处理一个前缀和数组s，其中s[i]表示区间[0,i]的区间和，那么我们很容易得出s[i]的递推式 s[i]=s[i−1]+w[i],s[0]=w[0]
根据上述式子，我们可以得到一个前缀和数组，如下图所示
我们知道，对于区间[0,i]的前缀和为s[i]，区间[0,j]的前缀和为s[j]，则区间[j,i]的前缀和为s[i]−s[j−1]，具体计算方式如下：
[j:i]区间和=w[i]+w[i+1]+...w[j]
s[i]=w[0]+w[1]+...w[i] (1)
s[j−1]=w[0]+w[1]+...w[j−1] (2)
根据(1),(2)式子作差可得：[j:i]区间和=s[i]−s[j−1]
因此，我们只需要预处理出前缀和数组，就可以根据上述计算公式，快速地计算出任意一个区间的区间和，在实际笔试或者面试中，为了减少边界情况的考虑，我们更习惯性地将数组下标设置为从1开始。
2. 应用场景
2.1 一维前缀和
主要是用于快速地求解某一个区间和，但是前缀和是静态的算法，就是说这个数组中每一个元素的值不能被修改，如果要一边修改一边动态查询，就需要使用树状数组或者线段树这种数据结构来实现动态查询。
2.2 二维前缀和
主要是针对二维场景，比如对于一个矩阵，矩阵的长度为n，宽度为m，它对应有n∗m个整数点，每一个点对应的权值不同，使用二维前缀和可以快速求出起点为(x1,y1)，终点为(x2,y2)的小矩形的权值和。
注意：本算法一般是基础算法，笔试中很少会单独考察，一般会结合哈希表/数组，动态规划，贪心等算法考察。
3. leetcode举例
3.1 寻找数组的中心下标
3.1.1 题目描述
给你一个整数数组 nums ，请计算数组的 中心下标 。
数组 中心下标 ****是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
3.1.2 举例
示例 1：
输入： nums = [1, 7, 3, 6, 5, 6]
输出： 3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
示例 2：
输入： nums = [1, 2, 3]
输出： -1
解释：
数组中不存在满足此条件的中心下标。
示例 3：
输入： nums = [2, 1, -1]
输出： 0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。
提示：
1 <= nums.length <= 104-1000 <= nums[i] <= 1000
3.1.3 解题
经典解法
class Solution {
public int pivotIndex(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
int left = 0;
for (int i = 0; i < nums.length; i++) {
if (left == sum - left - nums[i]) {
return i;
}
left += nums[i];
}
return -1;
}
}
3.2 560. 和为K的子数组
3.2.1 题目描述
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 *该数组中和为 k ***的子数组的个数 。
子数组是数组中元素的连续非空序列。
3.2.2 举例
示例 1：
输入： nums = [1,1,1], k = 2
输出： 2
示例 2：
输入： nums = [1,2,3], k = 3
输出： 2
提示：
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
3.2.3 代码
前缀和 + HashMap
class Solution {
public int subarraySum(int[] nums, int k) {
if (nums.length == 0) {
return 0;
}
HashMap<Integer,Integer> map = new HashMap<>();
//细节，这里需要预存前缀和为 0 的情况，会漏掉前几位就满足的情况
//例如输入[1,1,0]，k = 2 如果没有这行代码，则会返回0,漏掉了1+1=2，和1+1+0=2的情况
//输入：[3,1,1,0] k = 2时则不会漏掉
//因为presum[3] - presum[0]表示前面 3 位的和，所以需要map.put(0,1),垫下底
map.put(0, 1);
int count = 0;
int presum = 0;
for (int x : nums) {
presum += x;
//当前前缀和已知，判断是否含有 presum - k的前缀和，那么我们就知道某一区间的和为 k 了。
if (map.containsKey(presum - k)) {
count += map.get(presum - k);//获取次数
}
//更新
map.put(presum,map.getOrDefault(presum,0) + 1);
}
return count;
}
}
3.3 1248. 统计优美子数组
3.3.1 描述
给你一个整数数组 nums 和一个整数 k。如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
请返回这个数组中 「优美子数组」 的数目。
3.3.2 举例
示例 1：
输入： nums = [1,1,2,1,1], k = 3
输出： 2
解释： 包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
示例 2：
输入： nums = [2,4,6], k = 1
输出： 0
解释： 数列中不包含任何奇数，所以不存在优美子数组。
示例 3：
输入： nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出： 16
提示：
1 <= nums.length <= 500001 <= nums[i] <= 10^51 <= k <= nums.length
3.3.3 代码
前缀和+HASHMAP
class Solution {
public int numberOfSubarrays(int[] nums, int k) {
if (nums.length == 0) {
return 0;
}
HashMap<Integer,Integer> map = new HashMap<>();
//统计奇数个数，相当于我们的 presum
int oddnum = 0;
int count = 0;
map.put(0,1);
for (int x : nums) {
// 统计奇数个数
oddnum += x & 1;
// 发现存在，则 count增加
if (map.containsKey(oddnum - k)) {
count += map.get(oddnum - k);
}
//存入
map.put(oddnum,map.getOrDefault(oddnum,0)+1);
}
return count;
}
}
前缀和+数组
class Solution {
public int numberOfSubarrays(int[] nums, int k) {
int len = nums.length;
int[] map = new int[len + 1];
map[0] = 1;
int oddnum = 0;
int count = 0;
for (int i = 0; i < len; ++i) {
//如果是奇数则加一，偶数加0，相当于没加
oddnum += nums[i] & 1;
if (oddnum - k >= 0) {
count += map[oddnum-k];
}
map[oddnum]++;
}
return count;
}
}
3.4 904. 水果成篮（中等）
3.4.1 描述
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
- 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
- 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
3.4.1 具体说明
示例 1：
输入： fruits = [1,2,1]
输出： 3
解释： 可以采摘全部 3 棵树。
示例 2：
输入： fruits = [0,1,2,2]
输出： 3
解释： 可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
示例 3：
输入： fruits = [1,2,3,2,2]
输出： 4
解释： 可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
示例 4：
输入： fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出： 5
解释： 可以采摘 [1,2,1,1,2] 这五棵树。
提示：
1 <= fruits.length <= 1050 <= fruits[i] < fruits.length
3.4.3 解题思路
本道题可以抽象成一个数组， 选定一个子数组， 这个子数组最多只有两种数字，这个选定的子数组最大可以是多少。
前缀和+滑动窗口
public int totalFruit(int[] fruits) {
int left = 0,ans = 0;
Map<Integer,Integer> map = new HashMap<>();
for (int right = 0;right < fruits.length; right++) {
map.put(fruits[right], map.getOrDefault(fruits[right],0) + 1);
// 超过2个场地，滑动窗口就要左移，直至小于2个为止。
while (map.size() > 2) {
map.put(fruits[left],map.get(fruits[left]) - 1);
if (map.get(fruits[left]) == 0) {
map.remove(fruits[left]);
}
left ++;
}
ans = Math.max(ans,right - left + 1);
}
return ans;
}