[算法]前缀和

今天的每日一题是一道困难题,看了一下题解,然后就开始递归式的学习法,然后的然后就知道了一个叫前缀和的东西 :ku:

思想

本质上用空间换时间,即求一个数组和的时候,一般会写一个函数,直接进行一个数组历的遍

但是当这个函数要多次调用且函数的长度非常长的时候,每次调用都要遍历,开销还是特别大的,所以

可以在第一次遍历的过程中,引入一个数组进行前n个元素和的存储

注意,申请函数空间的时候,
int [] sum = new int[nums.length+1]

sum[i+1] = sum[i] + nums[i] //此处,sum[0]没有意义

返回求值的时候,可以求任意的下标i到j之间的元素和

return sum[j+1] - sum[i] //i+1时才把i加入,j+1时才把j加入

扩展

显然这还不够有趣,让我们来看看二维的情况

朴素代码如下:

public class NumMatrix {
    private int[][] sum;

    public void init(int [][] sum, int [][]nums){
        int m = nums.length;
        if(m==0){
            return;
        }
        int n = nums[0].length;
        sum = new int [m+1][n+1];
        //下标从1开始,注意与一维之间的区别
        for (int i = 1; i <= m ; i++) {
            for (int j = 1; j <= n ; j++) {
                sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + nums[i-1][j-1];
            }
        }
    }

    public int getSum(int row1,int col1,int row2,int col2){
        //千万注意下标!千万注意下标!千万注意下标!
        return sum[row2][col2]   + sum[row1-1][col1-1] - sum[row1-1][col2] - sum[row2][col1-1];
    }

}

添加和查询刚好是相反的

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注