一. 前缀和的简单介绍
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 证明初值无法覆盖所有的精力,取反+1
1.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<Integer,Integer> 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<Integer,Integer> 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