一. 前缀和的简单介绍

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

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

$pre[i] = \sum_{j=0}^{j=i}nums[j]$

数组的典型案例：

其他类型的前缀和多是最终能变成和数量相关，即转换成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）当 $s(i)='0'$ 且在前缀和 $pre[right]-pre[left-1]$ 不为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

原文链接： https://blog.csdn.net/weixin_45532984/article/details/129454244