Java算法题-前缀和

前言

       前缀和就是数组0-i位置的和，后缀和就是i- n - 1位置的和。其中i为数组中的任意下标，n为数组长度。前缀和的算法思想就是快速求得数组中某个区间内的和。下面我会用四道算法题详细的讲述该算法思想的运用。（Tip：题的难度是逐渐升级的，建议还不太了解该算法思想的朋友按照顺序阅读）。

1.前缀和

题目来源：【模板】前缀和_牛客题霸_牛客网

为大家简单说明一下题目要求：给出一个数组，并给你一个范围l和r,让你求出数组从下标l到下标r的和为多少。

但是注意的是，它会给出q组l和r的范围，所以你需要输出q个答案。并且数组你需要自己创建并接收输入台的数据放到数组中，牛客的题基本都是这样的，所以你自己得对 Scanner库熟悉才行。这里我就不过多赘述应该怎么接收数据，我主要讲这道题的算法思想。

1.1 解题思想

         首先暴力解法就是，每次给出新的范围l和r的时候，都去遍历一遍数组，当遍历到下标为l的时候开始累加，直到下标为r时累加结束，退出循环。此时的累加结果就是范围区间和。但是每次查询都要遍历一遍数组，不是很麻烦吗？而且会有大量的重复计算，比如第一次查询l为1，r为5，第二次查询l为1，r为3。在第一次查询的时候就已经遍历过(1-3)这个区间范围了，能不能在每次查询的时候都保存这个状态呢？比如第一次查询的时候在累加的时候就用一个二维数组vis[i][j]保存i-j区间的和。或者说在查询之前，直接就把vis表填好，在查询的时候直接去对照。但是这样的时间复杂度就变为n²了（因为i和j的取值范围都是大于等于0小于n）。

       所以有没有更好的方法呢？其实如果能想到用一张表（这里指的新的数组，其实也可是其他数据结构，视具体情况而定）保存重复计算的结果，就已经与这道题的真正算法思路挂钩了。可以直接用一维数组dp保存结果，这个一维数组会存放0-i位置的和，再由它计算出某个区间的和。如下图：

        如果我们想找L到R区间的和，那么只需在dp表中查找到dp[R]的值，再找到dp[L- 1]的值，两者相减即可，注意是L- 1，不能是L，因为不能把L下标所在的值也减掉，题目需要的是两个闭区间的区域和。

        讲到这里如果了解过动态规划的朋友就会知道这其实是一道非常简单的动态规划题（如果不了解也没关系）。思路讲到这里其实还有一个非常重要的细节，就是题目给出的范围是1 ≤ l ≤ r ≤ n，也就是表明数组应该是从下标1开始的，为了一一对应，所以我们在创建数组的时候需额外多创建一个空间，并且接收数组数据的时候从下标为1开始接收。所以dp数组也要多开一个空间。

1.2 代码实现

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(); // 获取数组长度
        int q = in.nextInt(); // 获取查询次数
        int[] arr = new int[n + 1]; // 接收数组数据
        for(int i = 1; i <= n; i++){
            arr[i] = in.nextInt();
        }
        long[] dp = new long[n + 1]; // 创建查询表，用long接收是因为区域和会很大防止数据溢出
        for(int i = 1; i <= n; i++){ // dp填表
            dp[i] = dp[i - 1] + arr[i]; // dp[i]等于0 到 i-1位置的和加上arr[i]
        }
        for(int i = 0; i < q; i++){
            int l = in.nextInt(), r = in.nextInt();
            System.out.println(dp[r] - dp[l - 1]);
        }
    }
}

2. 和为k的子数组

        题目来源：LCR 010. 和为 K 的子数组 - 力扣（LeetCode）

2.1 解题思想

        这道题让求和为k的子数组，其实就是在找区域和为k的区域有几个。有了上一题的铺垫已经知道了如何快速求某个区域的和。所以首先应该创建一个dp表保存状态，然后遍历nums数组，查询每个区域的和，左右边界的取值范围都是0到n-1，所以时间复杂度变为了n²。

        代码实现如下：

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n + 1]; 
        for(int i = 1; i <= n; i++){
            dp[i] = dp[i - 1] + nums[i - 1];
        }
        int ret = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++){
                if(dp[i] - dp[j - 1] == k) ret++;
            }
        }
        return ret;
    }
}

        上面这种代码虽然也能提交成功，但是时间性能不太好，也并不是该题我想讲的真正解法，后面我会在此基础上优化。在此之前，我想详细讲述一下上述这种代码容易踩的坑，熟悉动态规划的朋友就知道dp表的状态转移方程有时会出现数组下标越界的情况，一般处理有两种方法，一种是初始化，另外一种是额外加1个空间。在第1题里面，我们采用的就是额外加一个空间的方法。让dp从1开始，这样dp[i -1]就不会存在越界的情况，但是于此同时dp表和nums数组的对应关系就发生了变化，dp[i]对应的应该是nums[i - 1]。如果觉得理解有点困难的同学，可以这样理解，原本等式应该是：

dp[i] = dp[i - 1] + nums[i];

        但是这样会使得i为0时，dp发生下标越界。所以我们必须从下标1开始执行循环，或者在在i为0的时候做一个判断直接让dp[i] = num[i]，这样会使得代码比较臃肿而且每次循环都要多一个if判断。这个时候就可以把i等于0的情况，直接拿到循环外面，也就是之前讲的另外一种方法初始化。在循环外面直接让dp[0] = nums[0],然后循环直接从i = 1开始。这些方法都可行，看你更喜欢哪一种。但是个人习惯觉得前面的都会比较臃肿，我喜欢额外加一个空间的做法。相当于dp数组加了一个虚拟位置0，真正的对应是从dp[1]开始的，dp[1]对应第一个位置nums[0]。所以dp[i]对应dp[i -1]。dp[0]对应nums[-1]，这是越界的，但是还是要从文字逻辑上去想dp[0]应该等于什么，dp[0]表示nums数组中不存在的数组区域和，那其实就是0,因为根本不存在。又因为dp数组默认每个位置就是0，所以我们不用显示的去设置dp[0] = 0。这里之所以论述这么多，是因为不是每次dp[0]都为0的，要用逻辑文字的思想去想dp[0]为多少。但是一般都是为0，所以用这种方法解决dp越界问题就会显得很简洁。

       有些同学可能对下面这个循环有点疑惑，你可以把i和j想成左右边界l和r，这个循环就是在列举所有l和r排列的可能，然后判断区域和是否为k。i 和 j都从1开始，也是因为前面讲过在dp多开一个空间的情况下，从1开始才是有效位置。讲得比较详细一点，希望能对大家有帮助。

for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++){
                if(dp[i] - dp[j - 1] == k) ret++;
            }
  }

        回到正题，如何优化？主要就是上面这个嵌套循环能不能把里面的一层省略。里层的循环其实就是在找在1 - i位置中有没有一个位置，使得dp[i] - k 等于该位置的前缀和。当然这个位置可能有多个。如下图所示，j和m都是合法位置。

        快速查找前缀和dp[i] - k的位置有几个，就可以使用数据结构Map。把dp表中每个位置的前缀和都放入map中，然后直接查询即可。就可以省略里层循环。

        细节1：需要先map.put(0,1)，因为dp[i]也可以为k。细节2：需要先查询再放入dp[i]的值。因为我们需要的是在i之前是否存在这样的位置j的前缀和为dp[i] - k，这样dp[j + 1] 到 dp[i]的值就可以为k，如果在map中先放入了dp[i]，就相当于把i位置也包括进去了，但是j是不能等于i的，因为等于i之后，就表示是dp[i + 1]到dp[i]的值为k,这是不符合规范的左右边界。

2.2 代码实现

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n + 1]; 
        for(int i = 1; i <= n; i++){
            dp[i] = dp[i - 1] + nums[i - 1];
        }
        int ret = 0;
        Map<Integer, Integer> hash = new HashMap<>();
        hash.put(0,1); // 要先放入前缀和为0并设置为1次，处理dp[i] = k的情况
        for(int i = 1; i <= n; i++){
            ret += hash.getOrDefault(dp[i] - k, 0); // 先查询
            hash.put(dp[i], hash.getOrDefault(dp[i], 0) + 1); // 后放入
        }
        return ret;
    }
}

在此基础上可以再进行空间优化，因为有map了，所以我们无需再开一个数组空间dp去保存状态，直接用一个变量sum，在遍历数组的时候就存放进map里面。

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length, sum = 0;
        int ret = 0;
        Map<Integer, Integer> hash = new HashMap<>();
        hash.put(0,1); // 要先放入前缀和为0并设置为1次，处理dp[i] = k的情况
        for(int x : nums){
            sum += x;
            ret += hash.getOrDefault(sum - k, 0); // 先查询
            hash.put(sum , hash.getOrDefault(sum , 0) + 1); // 后放入
        }
        return ret;
    }
}

3.和可被K整除的子数组

题目来源：974. 和可被 K 整除的子数组 - 力扣（LeetCode）

 3.1 解题思想

        该题跟上题思路一样，可以使用双层循环找到一个位置j，使得j + 1位置到 i 位置的区域和可以被k整除，也就是（dp[i] - dp[j]）% k == 0, 找到一个满足条件的就让ret++,两层循环结束后返回ret即为结果。时间复杂度为n²，太低效了。可以用引入map，把查找j位置的时间复杂度从O(n)降为O(1)。但难点就在这里，上一题我们通过dp[i] - k的条件判断前面是否存在一个位置j,使得j + 1到i位置的和为k。但是这里应该用什么条件判断j + 1位置到i位置的和可以被k整除呢？

        这里就要讲到同余定理了：

        这里看到很多人讲同余定理的时候，都说前提是a和b必须非负，但其实a和b只要同号，这个等价等式就成立，比如a为-2，b为-2，k为4的时候，同样是负数，但是等价等式依然成立。在Java的模（%）运算中，余数一直和被除数的符合一致，但在数学定理中数学中的“取模”通常定义为非负余数。所以在该题中无论k是否大于0，只要a,b同号，同余定理就成立。

        首先要知道为什么在同号的情况下同余定理成立，这和接下来题目中我们处理余数为负的情况息息相关，很多其他题解都是只说了要把负余数修为正，但是却没有详细的证明和解释。所以接下来我会详细证明。

        a 和 b同号的情况：

 那异号为什么不成立呢，因为异号的话，余数不是相互抵消的，而是相加的。假设a > 0, b < 0,此时a - b相当于就是让a增大了b的绝对值这么多, 所以要使得（a - b）成为k的倍数说明a%k多余的部分加上b绝对值%k多余的部分，恰好能组成k。详细如下图：

 3.2 代码实现

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int ret = 0, sum = 0, n = nums.length;
        Map<Integer,Integer> hash = new HashMap<>();
        hash.put(0,1);
        for(int x : nums){
            sum += x;
            ret += hash.getOrDefault(sum % k, 0);
            ret += hash.getOrDefault(sum % k - k, 0);
            ret += hash.getOrDefault(sum % k + k, 0);
            hash.put(sum % k, hash.getOrDefault(sum % k, 0) + 1); 
        }
        return ret;
    }
}

细节优化，可以把余数为负的情况在存入map的时候就修改为非负数。如何修改才不会改变原来的结果正确匹配呢？首先肯定是不会影响同号匹配的情况的，和为正数匹配和为正数余数相同的，正数的余数本来就没有被修改，所以不会影响，那负数匹配负数呢？虽然负余数被修改为正了，但是只要是负余数相同的也都会被修改为一样的正数，所以依然不会影响。难点在于异号匹配的时候，如何确保%k为正数的sum[i]如何匹配%k为负数的sum[j]，由前面的推理可知，异号情况下，两个余数的绝对值相加为k即可，所以余数为负数的情况可以修正为（sum % k + k）,但是如果这样做余数为正数的情况下 sum % k + k就大于k了，所以正确应该是（sum % k + k）% k,这样就可以不改变余数为正数原本的值，并且修正了负数的情况;

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int ret = 0, sum = 0, n = nums.length;
        Map<Integer,Integer> hash = new HashMap<>();
        hash.put(0,1);
        for(int x : nums){
            sum += x;
            int target = (sum % k + k) % k;
            ret += hash.getOrDefault(target, 0);
            hash.put(target, hash.getOrDefault(target, 0) + 1); 
        }
        return ret;
    }
}

4.连续数组

题目来源：525. 连续数组 - 力扣（LeetCode）

 4.1 解题思想

这道题跟前面的题很类似，按照之前题的常规套路就是dp表保存每个位置的前缀和，然后用两个循环枚举所有区域，然后判断是否该区域长度的一半是否等于该区域和的一半，如果相等则说明该区域具有相同数量的0和1。但是这样的解法是会超时的，于是想像前面的题一样优化掉第二层循环。

要想用map找出位置，首先得知道满足什么条件的位置j是有效的。该题需要满足的条件就是dp[i] - dp[j] = (i - j) / 2，只要满足该条件就表示下标j + 1到 i这个区域是具有相同数量的子数组。但是我们没有办法表示j,因为等式中还包含一个位置变量dp[j]。

回想一下之前的找和为k的连续子数组，那道题就可以很清楚的知道用什么条件找到j的位置，这道题也可以思维替换一下，找到0和1数量相同的区域，这个时候区域的和都是不确定的，有可能0和1数量相同的区域和有的为1有的为3，等等。但是如果把每个0都替换成-1，是不是只要找到区域和为0的区域就表示0和1的数量相同了。此时就变成了找到和为0的最长子数组长度。

4.2 代码实现

class Solution {
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        int ret = 0, sum = 0;
        Map<Integer,Integer> hash = new HashMap<>();
        hash.put(0, -1);
        for(int i = 0; i < n; i++){
            if(nums[i] == 0) nums[i] = -1;
            sum += nums[i];
            if(hash.containsKey(sum)) ret = Math.max(ret, i - hash.get(sum)); // 存在就更新
            else hash.put(sum,i); // 不存在sum就放入
            
        }
        return ret;
    }
}

这里有个细节就是，如果在i之前map表就存在sum的值了，就无需更新坐标，因为我们求的是子数组的最长长度，所以坐标越前越好。保证map中每个不同的前缀和对应的都是数组中第一个前缀和为改值的下标。