算法——前缀和之一维前缀和模版、二维前缀和模版、寻找数组中心下标

此篇文章给大家分析关于前缀和算法的基本用法

我们要牢记一个思想：前缀和算法适合用于快速用来求数组中其中某一个连续区间的和

目录

1.一维前缀和模版

1.1解析

为什么dp数组的下标要从1开始??

1.2题解

2.二维前缀和模版

2.1解析

2.2题解

3.寻找数组的中心下标

3.1解析

3.2题解

---

1.一维前缀和模版

题目:【模板】前缀和_牛客题霸_牛客网

1.1解析

假设题目给我们提供了以上的数组,我们给这个数组提供下标(注意:在前缀和专题,数组的下标一般是从1开始的,这点后面会解释)

如果我们使用暴力解法,假设题目要求我们计算(2,4),即第2个元素到第4个元素的和,那么我们可以直接暴力计算出2~4元素的和

但是我们算一下时间复杂度:假设题目要我们计算q次,并且每次都要求我们计算整个数组的和,那么时间复杂度来到O(qn),我们看看题目的数据范围:1≤n,q ≤10^5

那么最大的时间复杂度可以来到10^10,一定会超时的

我们利用前缀和进行优化:

前缀和适合于快速用来求数组中其中某一个连续区间的和

具体算法分为两步

(1)预处理一个前缀和数组

建立一个数组(dp),dp[i]表示[1,i]区间的所有元素的和

(2)使用前缀和数组

其中最主要的是他的计算方式

如图所示:dp[1]表示1~1元素的和,由于是第一个元素,那么自然是他本身;

dp[2]表示1~2元素的和,那么就是1+2=3,dp[3]就是1~3元素的和,那么我们需要从第一个元素计开始累加计算吗??

当然不用,我们会发现,dp[i - 1]实际上已经保存了 1~i-1 的元素的和,那么我们在计算dp[i]的时候直接用dp[i-1] + arr[i]即可,这样我们就不用每次都从第1个元素开始累加了.而计算完dp数组的时间复杂度也仅仅是O(n);

其中:dp[i] = dp[i-1] + arr[i] 这个公式我们称为递推公式,注意:递推公式不能死记,因为每道题的递推公式有可能不一样,我们需要根据实际来自己写出公式

为什么dp数组的下标要从1开始??

我们会注意到:假如我们dp数组的下标是从0开始的,那么我们计算第一个元素时,由递推公式::dp[i] = dp[i-1] + arr[i],那么必然会出现dp[-1]的情况,为了解决这个问题只能分类讨论但是如果我们的下标从1开始,那么第一个元素就是dp[1] = dp[0] + arr[1],就不会出现越界的情况,但此时为了满足原数组的长度需求,我们dp数组的长度必须为n+1

回到这道题,当我们计算完dp数组后,假设题目要我们计算从L~R的元素之和,我们直接就可以利用dp数组快速得到结果:

如图,那么sum = dp[R] - dp[L-1]

那么这样的话,时间复杂度就为创建dp数组的 O(n) + 计算q次,那么就为O (n + q);

1.2题解

public class Main {
     public static void main(String[] args) {
         Scanner in = new Scanner(System.in);
         // 注意 hasNext 和 hasNextLine 的区别
         while (in.hasNextInt()) { // 注意 while 处理多个 case
         int n = in.nextInt();
         int q = in.nextInt();
         int[] arr = new int[n+1];
         for(int i = 1; i < n+1; i++){
             arr[i] = in.nextInt();
         }
         long[] dp = new long[n+1];
         for(int i = 1; i < n+1; i++){
             dp[i] = dp[i-1] + arr[i];
         }
         for(int i = 0; i < q; i++){
             int l = in.nextInt();
             int r = in.nextInt();
             System.out.println(dp[r] - dp[l-1]);
         }
         }
     }
 }

---

2.二维前缀和模版

题目:【模板】二维前缀和_牛客题霸_牛客网

2.1解析

题目会给我们提供一个n行m列的二维数组,要求我们计算(x1, y1) ~ (x2, y2)的元素和,且题目具体说明下标是从1开始的

如图所示,假设我们计算(1,1) ~ (2,2),即计算 1 + 2 + 3 + 2

当然这个过程利用暴力解法是可以的,但是时间复杂度来到O(n * m * q)

上一题我们说过,前缀和算法适用于快速用来求数组中其中某一个连续区间的和,在二维数组也一样可以.那么我们接下来利用前缀和算法来进行优化:

(1)预处理出来一个前缀和矩阵,还是dp

dp[i]表示从 [1,1] 位置到 [i,j]位置这段区间里面所有元素的和

假设我们要计算dp[i] [j],我们可以把这个区域的值的和分为上述几个模块,那么dp[i] [j] = A + B + C + D ,单独计算A当然是容易的,但是B和D就比较复杂,因为这两个模块都没有从原点开始的,而我们的dp数组记录的都是从原点开始计算的和.那么我们可以变化一下式子: 原式 =( A + B) +( A + C )+ D - A,这样 A + B模块就是 dp[i-1] [j], A + C模块就是dp[i] [j - 1],这样dp[i] [j] = dp[i-1] [j] + dp[i] [j - 1] + arr[i] [j] - dp[i-1] [j-1],递推公式就出来了

(2)使用前缀和矩阵

假设要计算(x1,y1) ~ (x2,y2)的数据之和,即D区域的数值和我们该怎么利用dp数值来计算呢??

按照上面创建dp数组的思路,不难发现.D = A + B + C + D - (A+B) - (A + C) + A即可计算

因此D= dp[x2] [y2] - dp[x1-1] [y2] - dp[x2] [y1 -1] + dp[x1-1] [y1-1]

这样我们就能直接计算二维数组某个范围的数值和

2.2题解

 public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int m = in.nextInt();
            int q = in.nextInt();
            int[][] arr = new int[n + 1][m + 1];
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    arr[i][j] = in.nextInt();
                }
            }
            long[][] dp = new long[n + 1][m + 1];
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= m; j++) {
                    dp[i][j] =  dp[i-1][j] + dp[i][j - 1] + arr[i][j] - dp[i-1][j-1];
                }
            }
            for (int i = 0; i < q; i++) {
                int x1 = in.nextInt();
                int y1 = in.nextInt();
                int x2 = in.nextInt();
                int y2 = in.nextInt();
                System.out.println(dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1 -1] + dp[x1-1][y1-1]);
            }
        }
    }

---

3.寻找数组的中心下标

题目:. - 力扣（LeetCode）

3.1解析

所谓中心下标就是数组中的某个元素,它左边所有元素的和 = 右边所有元素的和.并且假设是最左边 / 最右边的元素,那么它的左边 / 右边 元素的和默认为0,如果存在多个,那么返回第一个

这不就是典型的前缀和问题:用于快速用来求数组中其中某一个连续区间的和,而这道题我们不仅仅是计算前缀和,还要计算后缀和

我们用f来表示前缀和数组,用g来表示后缀和数组,那么f[i] 表示 [0,i-1]区间内所有元素的和,因为计算中心元素时,这个元素是不算在内的,所以是i-1;而g[i]表示[i+1,n-1]区间内所元素的和;

不难推出,f[i] = f[i-1] + arr[i-1],g[i] = g[i+1] + arr[i+1]

但是有一个细节问题,与前面不同的是,我们的前缀和 / 后缀和数组都是要从0开始的,因为数组是给定的,下标从0开始的,那么我们就要考虑特殊情况,即左边界和右边界,那么我们就要先设定f[0] = g[n-1] = 0

在创建好前缀和数组和后缀和数组后,我们只需要再次遍历原数组,判断f[i] == g[i]即可

3.2题解

class Solution {
    public int pivotIndex(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int[] g = new int[n];
        for(int i = 1; i < n; i++){
            f[i] = f[i-1] + nums[i-1];
            g[n-1-i] = g[n-i] + nums[n-i];
        }
        for(int i = 0; i < n; i++){
            if(f[i] == g[i]){
                return i;
            }
        }
        return -1;
    }
}