tag数组-刷题预备知识-6. 数组的前缀和(preSum), lt.303 + lt.304

前缀和一般用来用作区间求和, 它的每个值都是从**左边最初始位置的数(如下标0)**到它本身的和

前缀和的主要使用场景: 原始数组不会被修改的情况下, 频繁查询某个区间的累加和, 原始数组不改变是相对于差分法来讲的.

其实可以把它理解为数学上的数列的前n项和（对于一个一维数组的前缀和）。我们定义对于一个数组a的前缀和数组s，s[i] = a[1]+a[2]+…+a[i].

比如数组[1,3,5,7]的前缀和为[1,4,6,8], 借助前缀数组, 我们可以求出某一段区间的和.

比如, 下面这道典型的前缀和题目

[案例需求]

[思路分析]

这道题我们最先想到的应该是暴力解法: 给你一个区间(left, right), 然后我们在这个区间里面遍历, 并把遍历到的和加起来后返回的结果即最终结果; 这种解法的复杂度为O(n), 时间复杂度取决于区间的长度, 如果题目给出了多个区间让你返回值的话, 那么每一次我们都需要遍历区间进行计算, 每一次调用的时间复杂度都是O(n);通过前缀和解法, 我们在初始化数组的方法中, 新建一个前缀和数组 preSum[],

这个数组中存放的是从0->i每个区间的和, 比如原始数组[1,2,3,4], 前缀和数组为[0, 1, 3, 6, 10],为了便于理解, 我们定义的前缀和数组都是从0开始, 数组的长度也因此比原始数组多一位,但是这样写就需要特别注意: nums[i - 1]对应于preSum[i]的区间和, 比如原始数组index为1的区间和(1 + 2)为前缀和数组index为2的值

[代码实现]

一, 易于理解的暴力解法

class NumArray {

    private int[] preSum;
    public NumArray(int[] nums) {
        //初始化数组
        this.nums = nums;
    }
    //区间和相关方法
    public int sumRange(int left, int right) {
        int sum = 0;

        for(int i = left; i <= right; i++){
             sum += nums[i];
         }
         return sum;
    }
}

二, 对于求区间和最优的前缀和解法

class NumArray {

    private int[] preSum;
    public NumArray(int[] nums) {
        // //初始化数组
        // this.nums = nums;
        

        //2. 前缀和解法, 新建一个数组, 存放从 0->i个元素的和
        preSum = new int[nums.length + 1];

        //存放元素的前缀和
          遍历原数组, 把叠加 pre[j - 1] + nums[j - 1], 放入到 preSum[j]中
        for(int j = 1; j <= nums.length; j++){
            preSum[j] = preSum[j - 1] + nums[j - 1];
        }
    }
    
    public int sumRange(int left, int right) {
        return preSum[right + 1] - preSum[left];
    }
}

么看懂? 力扣题解

[思路分析]

本题通过画图的方法非常容易理解, 主要容易 出错的地方跟上面一样, 由于前缀和数组从前缀和为0的数开始, 原始数组下标要特别注意跟前缀和数组对应上! 比如preSum[i] 为原始数组nums[i - 1]的前缀和;本题带图题解: 力扣题解

[代码实现]

class NumMatrix {
    
    int[][] preSum;

    public NumMatrix(int[][] matrix) {
        //初始数组, 求出每个框的和
        preSum = new int[matrix.length + 1][matrix[0].length + 1];

        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[i].length; j++){
                preSum[i + 1][j + 1] = matrix[i][j] + preSum[i][j + 1] + preSum[i + 1][j] - preSum[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return preSum[row2 + 1][col2 + 1] - preSum[row2 + 1][col1] - preSum[row1][col2 + 1] + preSum[row1][col1];
    }
}