数组之前缀和

水深无声 2023-10-13 12:00 31阅读 0赞

#### 1.前缀和 ####

前缀和的概念:前缀和是指数组中从开始位置到当前位置的所有位置的元素之和,它可以通过累加数组元素来计算,一般来说,我们可以使用前缀和数组在常数时间复杂度内计算任意区间的和.

注意:特别是需要频繁的计算区间和的情况,可以通过先预先计算前缀和数组,可以将时间复杂度从O(n)降到O(1)

##### 1.一维数组前缀和 #####

class NumArray {
        private int[] preSum;
        //构造前缀和数组
        public NumArray(int[] nums) {
          int n=nums.length;
          preSum=new int[n+1];
         for(int i=1;i<preSum.length;i++){
             preSum[i]=preSum[i-1]+nums[i-1];
         }
        }
        //查询(left,right)中的元素之和
        public int sumRange(int left, int right) {
         return preSum[right+1]-preSum[left];
        }
    }

##### ![cd8f82eaef3247c4a1c1143e5a1b34e9.png][] #####

##### 2.二维数组前缀和 #####

class NumMatrix {
        //构造二维数组
        private int[][] preSum;
        public NumMatrix(int[][] matrix) {
         int row=matrix.length;
         int colum=matrix[0].length;
         preSum=new int[row+1][colum+1];
         for(int i=1;i<preSum.length;i++){
             for(int j=1;j<preSum[0].length;j++){
                 preSum[i][j]=preSum[i-1][j]+preSum[i][j-1]+matrix[i-1][j-1]-preSum[i-1][j-1];
             }
         }
        }
        
        public int sumRegion(int row1, int col1, int row2, int col2) {
           return preSum[row2+1][col2+1]-preSum[row1][col2+1]-preSum[row2+1][col1]+preSum[row1][col1];
        }
    }

![f7122170437c4c59b556272bb83bdccb.png][]

假设如果现在有一个二维数组,让你去求二维数组的前缀和怎么算?

![979f6fdf7c4b4a399e124a5380c6fc55.png][]

我们首先要创建一个n+1长度的二维数组

![3e6afc1a1ffa40c3aa0a5b453c32101b.png][]

我们在这里先要知道二维数组的面积是怎么算的

![409befa1afc4455c93aee8dcabbf21b6.png][]

![8d17fed33e3242b2b3464d6d0c92f706.png][]

[cd8f82eaef3247c4a1c1143e5a1b34e9.png]: https://img-blog.csdnimg.cn/cd8f82eaef3247c4a1c1143e5a1b34e9.png
[f7122170437c4c59b556272bb83bdccb.png]: https://img-blog.csdnimg.cn/f7122170437c4c59b556272bb83bdccb.png
[979f6fdf7c4b4a399e124a5380c6fc55.png]: https://img-blog.csdnimg.cn/979f6fdf7c4b4a399e124a5380c6fc55.png
[3e6afc1a1ffa40c3aa0a5b453c32101b.png]: https://img-blog.csdnimg.cn/3e6afc1a1ffa40c3aa0a5b453c32101b.png
[409befa1afc4455c93aee8dcabbf21b6.png]: https://img-blog.csdnimg.cn/409befa1afc4455c93aee8dcabbf21b6.png
[8d17fed33e3242b2b3464d6d0c92f706.png]: https://img-blog.csdnimg.cn/8d17fed33e3242b2b3464d6d0c92f706.png