算法|前缀和解法

算法笔记

发布日期: 2022-05-02

更新日期: 2024-01-10

文章字数: 1.3k

阅读时长: 5 分

阅读次数:

前置知识：

基本数据结构知识(数组)

Java中HashMap容器基本了解

文章目的：

文章为笔记记录和一些思考，是对应 labuladong 的刷题秘籍记录，下边贴出 labuladong 官方链接

labuladong 的算法小抄 :: labuladong的算法小抄

介绍

顾名思义，前缀和的意思就是一段数字中，某一个数字前面一段数字的和。在数组中解释的意思就是，数组索引前面的数据和。我们常用一个新数组（索引错位值为1）来记录数组的前缀和，以此辅助我们更好的解决数组中某一段数据和的问题。下图中 nums 为数组， preSum 为前缀和。

计算前缀和的原始思路：$sumRange(i,j)=\sum_{k=i}^{j}nums[k]$
升级后前缀和的计算思路为：$sumRange(i,j)=\sum_{k=0}^{j}nums[k]-\sum_{k=0}^{i-1}nums[k]$
用数组 $sums$ 记录对应 $nums$ 索引的前缀和，$sum$ 的长度为 $n+1$ （方便计算，无需对 $i=0$ 做特殊处理），其满足 $sums[i+1] = sums[i]+nums[i]$ ，

即$sums[i+1]$ 表示 $\sum_{n=0}^{i}nums[n]$ 。那么有 $sumRange(i,j)=sums[j+1]-sum[i]$

题目

区域和检索 - 数组不可变 - 力扣（LeetCode）

题目大意：

计算数组 nums 中 $nums[left]$ 到 $nums[right]$ 的元素和，

//标准前缀和思路，直接使用前缀和即可解题
class NumArray {
//	全局初始化前缀和
    int preNum[];

    public NumArray(int[] nums) {
//      在构造函数中就建立好前缀和数组，让 sumRange 被多次调用时候减少运算
        preNum = new int[nums.length +1];
        for(int i = 1 ;i < preNum.length; i++){
            preNum[i] = preNum[i-1] + nums[i-1];
        }
    }
    
    public int sumRange(int left, int right) {
          return preNum[right+1] - preNum[left];  
    }
}

二维区域和检索 - 矩阵不可变 - 力扣（LeetCode）

题目大意：

在一个二维矩阵 matrix 里面，任意选两个点，计算这两点所形成的子矩阵的元素总和

class NumMatrix {
//	全局初始化前缀和邻接数组
    int[][] preNum;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        preNum = new int[m+1][n+1];
        for (int i = 1; i <= m ; i++){
            for(int j = 1; j <= n ; j++){
            //  二维前缀和  
                preNum[i][j] = preNum[i-1][j] + preNum[i][j-1] + matrix[i-1][j-1] - preNum[i-1][j-1];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
     //   由二维前缀利用四则运算得出子矩阵元素和
        return preNum[row2+1][col2+1] - preNum[row1][col2+1] - preNum[row2+1][col1] + preNum[row1][col1];
    }
}

二维前缀和

由二维前缀利用四则运算得出子矩阵元素和

和为 K 的子数组 - 力扣（LeetCode）

题目：

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

//直接使用前缀和+双重遍历枚举的解法
class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length +1;
        int preNum[] = new int [n];
        for(int i = 1;i <= nums.length; i++ ){
            preNum[i] = preNum[i-1] + nums[i-1];
        }
        int result = 0;
        for(int i = 1;i < n;i++){
            for(int j = 0;j < i;j++ ){
                //双重遍历，计算出满足的数
                if((preNum[i] - preNum[j])  == k) result++;
            }
        }
        return result;
    }
}

由此提交记录可知该算法的执行用时比较大，我们可以再次优化该算法

优化思路

该算式 $preNum[i] - preNum[j] = k$ 为判断是否符合条件的核心式子，对该式子进行简单的变换 $preNum[i] - k = preNum[j]$。利用该式子和哈希表，使用一轮遍历将前缀和以及满足 k 的 result记录下来，继而达到优化的目的。

HashMap 中的 key 记录的是前缀和，value 记录的是该 key 出现的次数。在每一轮遍历检测中，当容器中的 key 存在等于式子 $preNum[i] - k = preNum[j]$ 中的 preNum[j] 的情况时，则让 result 累加该 key 的 value 。

遍历完整个数组后，所有符合条件的 key 都被找出并累加到 result 中

其中，当 $key=0$ 时，设置 $value=1$ 是由于当该前缀和被创建时候，未添加值的时候，前缀和就是 0 。这样子也才能保证第一次得出 $key=0$ 时，其对应值 value 为 1。

注：HashMap 不会允许多个相同的 key 值存在，因此，上例中只有一个 $key=8$ 存在，只是 value 不断在被更改，图像这样子画出来只是为了方便理解

class Solution {
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        HashMap<Integer,Integer> preNum = new HashMap<>();
        preNum.put(0,1); //这里不可缺，相当于添加了个队头(前缀和为0)，这是只要有队就存在的
        int result = 0;
        int s_i = 0;
        for(int i = 0; i < n;i++){
            s_i += nums[i];
            int s_j = s_i - k;
            if(preNum.containsKey(s_j)) {
                //累加对应 key 中的 value
                result += preNum.get(s_j);
            }
            //记录 key 出现的次数
            preNum.put(s_i,preNum.getOrDefault(s_i,0) + 1);
        }
        return result;
    }
}