一. 前缀和的简单介绍

1.前缀和的数组型简单定义

对于数组nums来说，前缀和pre[i] = pre[i-1] + nums[i]，即每个位置上存储的是前i个数组元素的和，用数学公式表示为：

数组的典型案例：

其他类型的前缀和多是最终能变成和数量相关，即转换成int[] 数组类型。

那么，对于后缀和是一样的道理。 

 2.前缀和的典型使用场景/触发关键词

        在一些题目或者场景中，出现了子数组*，连续一段区间，并且和求数量或者判断数量相关，很大程度上可以向前缀和的方去思考。

二. 使用前缀和的经典案例 

1.leetcode1413 逐步求和得到正数的最小值

给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。

你需要从左到右遍历 nums 数组，并将 startValue 依次累加上 nums 数组中的值。

请你在确保累加和始终大于等于 1 的前提下，选出一个最小的 正数 作为 startValue 。

输入：nums = [-3,2,-3,4,2]
输出：5
解释：如果你选择 startValue = 4，在第三次累加时，和小于 1 。累加求和startValue = 4 | startValue = 5 | nums(4 -3 ) = 1  | (5 -3 ) = 2    |  -3(1 +2 ) = 3  | (2 +2 ) = 4    |   2(3 -3 ) = 0  | (4 -3 ) = 1    |  -3(0 +4 ) = 4  | (1 +4 ) = 5    |   4(4 +2 ) = 6  | (5 +2 ) = 7    |   2

对于本题，可以转化为求一类最小值问题，即前缀和中出现的最小值，即在遍历整个数组时，可能出现的最小值，即

只要最小值能够满足要求，那么在其他位置上也可以满足要求，上述出现的sum(1)~sum(n)即为典型的前缀和的概念，换个思路，此题目在求能使得数组通过的最小宽度，即

前缀和解答

class Solution {public int minStartValue(int[] nums) {int[] dp = new int[nums.length];int min = nums[0];dp[0] = nums[0];for(int i = 1; i < nums.length; i++){dp[i] += dp[i-1]+nums[i];if(dp[i] < min){min = dp[i];}}if(min > 0) return 1;return 1-min;}
}

动态规划空间优化 

对于上述解答来说，由于当前值只和nums[i]和上一个值有关，用两个变量保存交替前进即可

class Solution {public int minStartValue(int[] nums) {int min = 0;int pre = 0;for(int i = 0; i < nums.length; i++){pre += nums[i];if(pre <= min){min = pre;}}if(min > 0) return 1;return 1-min;}
}

 本题小结：（1）此题是前缀和的最简单应用，最终的答案和前缀和的最大值相关

2.leetcode2383 赢得比赛需要的最少训练时长

你正在参加一场比赛，给你两个 正 整数 initialEnergy 和 initialExperience 分别表示你的初始精力和初始经验。

另给你两个下标从 0 开始的整数数组 energy 和 experience，长度均为 n 。

你将会 依次 对上 n 个对手。第 i 个对手的精力和经验分别用 energy[i] 和 experience[i] 表示。当你对上对手时，需要在经验和精力上都 严格 超过对手才能击败他们，然后在可能的情况下继续对上下一个对手。

击败第 i 个对手会使你的经验 增加 experience[i]，但会将你的精力 减少  energy[i] 。

在开始比赛前，你可以训练几个小时。每训练一个小时，你可以选择将增加经验增加 1 或者 将精力增加 1 。

返回击败全部 n 个对手需要训练的 最少 小时数目。

输入：initialEnergy = 5, initialExperience = 3, energy = [1,4,3,2], experience = [2,6,3,1]
输出：8
解释：在 6 小时训练后，你可以将精力提高到 11 ，并且再训练 2 个小时将经验提高到 5 。
按以下顺序与对手比赛：
- 你的精力与经验都超过第 0 个对手，所以获胜。精力变为：11 - 1 = 10 ，经验变为：5 + 2 = 7 。
- 你的精力与经验都超过第 1 个对手，所以获胜。精力变为：10 - 4 = 6 ，经验变为：7 + 6 = 13 。
- 你的精力与经验都超过第 2 个对手，所以获胜。精力变为：6 - 3 = 3 ，经验变为：13 + 3 = 16 。
- 你的精力与经验都超过第 3 个对手，所以获胜。精力变为：3 - 2 = 1 ，经验变为：16 + 1 = 17 。
在比赛前进行了 8 小时训练，所以返回 8 。
可以证明不存在更小的答案。

class Solution {public int minNumberOfHours(int initialEnergy, int initialExperience, int[] energy, int[] experience) {int preen = initialEnergy;int preex = initialExperience;int exermax = 0;int len = energy.length;for(int i = 0; i < len; i++){preen -= energy[i];if(preex <= experience[i]){int diff = experience[i]-preex+1;exermax = Math.max(exermax,diff);}preex += experience[i];}if(preen <= 0){preen = 0-preen+1;} else{preen = 0;}return preen + exermax;}
}

1. 对于精力来说，一直减少，那么直接一直减去就好了

        1.1 最后小于0 证明初值无法覆盖所有的精力，取反+11.2 最后大于0 证明初值可以覆盖所有的精力，不需要额外的精力

2. 对于经验来说，适当更新（特定地方更新）

        2.1 当前缀和无法覆盖当前经验，进行更新，更新的值是前缀和与当前值的差值2.2 当前缀和可以覆盖当前经验，无需额外的经验

本题小结：（1）本题目只需要在经验部分使用前缀和，精力其实是符合贪心原则，即一直减去就好了，一直是最优值（最后需要的答案值）

                  （2）前缀和不需要留存，与数组当前值比较即可

三. 前缀和的好搭档：动态规划和HashMap

        在实际的题目中，单独使用前缀和可以解决问题，但有些题目受限于时间和空间复杂度，单独依靠前缀和往往不能AC，需要一些额外的技巧或者附加数据结构，例如动态规划和HashMap。

3.1 动态规划经常和前缀和一起使用

（1）leetcode1871 跳跃游戏 VII

给你一个下标从 0 开始的二进制字符串 s 和两个整数 minJump 和 maxJump 。一开始，你在下标 0 处，且该位置的值一定为 '0' 。当同时满足如下条件时，你可以从下标 i 移动到下标 j 处：

i + minJump <= j <= min(i + maxJump, s.length - 1) 且
s[j] == '0'.
如果你可以到达 s 的下标 s.length - 1 处，请你返回 true ，否则返回 false 。

输入：s = "011010", minJump = 2, maxJump = 3
输出：true
解释：
第一步，从下标 0 移动到下标 3 。
第二步，从下标 3 移动到下标 5 。

动态规划 

class Solution {public boolean canReach(String s, int minJump, int maxJump) {int n = s.length();boolean[] dp = new boolean[n];dp[0] = true;for (int i = minJump; i < n; i++){if (s.charAt(i) == '1')continue;int left = i - maxJump < 0 ? 0 : i - maxJump;int right = i - minJump;for (int j = left; j <= right; j++){if (dp[j]){dp[i] = true;break;}}}return dp[n - 1];}
}

在最基础的动态规划中，我们来到第i个位置，第i个位置能不能走到，取决于之前在i- maxJump~i- minJump中是否有一个位置j，这个位置j是可以走到的，那么可得知从j可以蹦到i，如果在i- maxJump~i- minJump范围内都是不可达的，那么证明第i个位置也是不可达的。

总结

动态规划的初始条件: dp[0] = True,默认第一个元素都是‘0’,都可以走到
动态规划的递推公式：f(i) = f(i-minJump) || f(i-minJump-1) || ... || f(i-maxJump)
动态规划的终止条件：来到数组最后一个位置

上述动态规划的时间复杂度肯定是很高的，在java语言下，勉强可以通过。

动态规划+前缀和

轮到前缀和出场：

class Solution {public boolean canReach(String s, int minJump, int maxJump) {int n = s.length();boolean[] f = new boolean[n];int[] pre = new int[n];f[0] = true;for(int i = 0; i < minJump; i++){pre[i] = 1;}for(int i = minJump; i < n ; i++){int left = i-maxJump;int right = i-minJump;if(s.charAt(i) == '0'){int total = pre[right] - (left <= 0 ? 0:pre[left-1]);if(total != 0) f[i] = true;}if(f[i]){pre[i] = pre[i-1] + 1;} else{pre[i] = pre[i-1];}}return f[n-1];}
}

本题小结：（1）在本种解法中，前缀和保存了一定区间内可达位置的数量，前缀和之差保存了目标区间可达数量

                  （2）当且在前缀和不为0时，i位置才可达，可达即要更新，即在上个区间的基础上加一：pre[i] = pre[i-1] + 1

3.2 HashMap，前缀和的另外一个好搭档

        在有些题目中，使用HashMap们可以极大地降低时间复杂度，尤其在解中出现两层以上for循环，其中的一层很有可能通过HashMap来优化。

（1）leetcode1590 使数组和能被 P 整除

给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。

请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。

子数组 定义为原数组中连续的一组元素。

输入：nums = [3,1,4,2], p = 6
输出：1
解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。

动态规划（已经部分优化过）

class Solution {public int minSubarray(int[] nums, int p) {int len = nums.length;int[][] dp = new int[len][len];int min = len;int sum = 0;int temp = 0;for(int i : nums){sum += i;temp += i;temp %= p;}if(temp % p == 0) return 0;for(int i = 0; i < len ; i++){for(int j = i; j < len ; j++){if(j == 0 && i == 0){dp[i][j] = nums[j];}else{dp[i][j] = dp[i][j-1] + nums[j];}int diff = sum-dp[i][j];if(diff == 0) continue;if( diff % p == 0){int dele = j-i+1;min = Math.min(min,dele);}}}if(min == len) return -1;return min;}
}

 空间上达不到要求

 前缀和优化

class Solution {public int minSubarray(int[] nums, int p) {int sum = 0;int pre = 0;//前缀和int min = nums.length;//保存最小值int len = min;HashMap map = new HashMap<>();for(int i : nums){sum = (sum+i)%p;}if(sum == 0) return 0;map.put(0,-1);for(int i = 0; i < len; i++){pre = (pre+nums[i]) % p;int target = (pre - sum + p) %p;if(map.containsKey(target)){int distance = i - map.get(target);min = Math.min(min,distance);}map.put(pre,i);}return min == len ? -1 : min;}
}

题目小结：（1）在本题中，若只依靠前缀和， 在两层for循环中，很容易造成时间和空间超标

                  （2）通过HashMap存储目标值，让时间复杂度变为O(N)

（2）面试题 17.05.  字母与数字

给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。

返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。
 

输入: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"]输出: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7"]

class Solution {public String[] findLongestSubarray(String[] array) {HashMap map = new HashMap<>();int ct_num_i = 0;int ct_cha_i = 0;int len = array.length;map.put(0,-1);int max = 0;int index = 0;for(int i = 0; i < len; i++){if(array[i].charAt(0) >= '0' && array[i].charAt(0) <= '9'){ct_num_i++;}else{ct_cha_i++;}int diff = ct_num_i - ct_cha_i;if(map.containsKey(diff)){int j = map.get(diff);if(i - j > max){max = i-j;index = j+1;}}else{map.put(diff,i);}}String[] ans = new String[max];for(int i = 0; i < max; i++){ans[i] =  array[index + i];}return ans;}
}

本体小结：（1）此题目和上题一样，也是用过HashMap来降低时间复杂度

                  （2）注意此题存储的是ct_num_i - ct_cha_i，因为只存储一个类型的数量，会导致无法处理未知值，详情可看下方图片中的红色虚线框，而存储差值就比较方便，因为当满足题目要求时，我们有：

ct_num_i - ct_cha_i == ct_num_ j - ct_cha_ j ，j为i之前的某个位置。

而int diff = ct_num_i - ct_cha_i 其中的diff正是差值。

 参考来源

【1】leetcode ylb [Python3/Java/C++/Go/TypeScript] 一题一解：前缀和 + 哈希表（清晰题解）

【2】leetcode 官方解题 跳跃游戏 VII