数据结构和算法-前缀和

451 次访问 2022-01-10

mood

前缀和

前缀和是一种重要的预处理，能大大降低查询的时间复杂度。可以简单理解为“数列的前N项的和”。

一维前缀和

给定前缀和数组B,和原数组A,递推关系有

B[0] = A[0]，对于i>=1 则 B[i] = B[i-1] + A[i]。

二维前缀和

二维前缀和的普通求解方法是基于容斥原理递推公式

给定二维数组A[m][n],数组P是A的前缀和数组。计算区域[x1,y1]-[x2,y2]的和:

sum=P[x2][y2]-P[x1-1][y2]-P[x2][y1-1+P[x1-1][y1-1]

如何计算前缀和数组P[i][j]？

P[i][j]=P[i-1][j]+p[i][j-1]-p[i-1][j-1]+A[i][j]

前缀和例题

长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
区域和检索 - 数组不可变

给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点。
实现 NumArray 类：
NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j 两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）
二维区域和检索 - 矩阵不可变

给定一个二维矩阵 matrix，以下类型的多个请求：
计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
实现 NumMatrix 类：
NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 所描述的子矩阵的元素总和。
矩阵区域和

给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：
i - k <= r <= i + k,
j - k <= c <= j + k 且
(r, c) 在矩阵内。

长度最小的子数组

代码实现

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int sum=0,l=0,minLen=Integer.MAX_VALUE;
        for(int r=0;r<nums.length;r++){
            sum+=nums[r];
            while(sum>=target){
                minLen=Math.min(minLen,r-l+1);
                sum-=nums[l++];
            }
        }
        return minLen==Integer.MAX_VALUE?0:minLen;
    }
}

区域和检索 - 数组不可变

代码实现

class NumArray {
    int[] sumArray;
    public NumArray(int[] nums) {
        sumArray=new int[nums.length+1];
        for(int i=0;i<nums.length;i++){
            sumArray[i+1]=nums[i]+sumArray[i];
        }
    }
    
    public int sumRange(int i, int j) {
        return sumArray[j+1]-sumArray[i];
    }
}

二维区域和检索 - 矩阵不可变

代码实现

type NumMatrix struct {
    PreSum [][]int
}


func Constructor(matrix [][]int) NumMatrix {
    m,n:=len(matrix)+1,len(matrix[0])+1
    preSum:=make([][]int,m)
    for i:=0;i<m;i++{
        preSum[i]=make([]int,n)
    }
    for i:=1;i<m;i++{
        for j:=1;j<n;j++{
            preSum[i][j]=preSum[i][j-1]+preSum[i-1][j]-preSum[i-1][j-1]+matrix[i-1][j-1]
        }   
    }
    return NumMatrix{
        PreSum:preSum,
    }

}


func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    return this.PreSum[row2+1][col2+1]-this.PreSum[row2+1][col1]-this.PreSum[row1][col2+1]+this.PreSum[row1][col1]
}


/**
 * Your NumMatrix object will be instantiated and called as such:
 * obj := Constructor(matrix);
 * param_1 := obj.SumRegion(row1,col1,row2,col2);
 */

矩阵区域和

代码实现

func matrixBlockSum(mat [][]int, k int) [][]int {
    m,n:=len(mat)+1,len(mat[0])+1
    sum:=make([][]int,m)
    for i:=0;i<m;i++{
        sum[i]=make([]int,n)
	}
    for i:=1;i<m;i++{
        for j:=1;j<n;j++{
			sum[i][j]=sum[i-1][j]+
			sum[i][j-1]-sum[i-1][j-1]+
			mat[i-1][j-1]

		}
	}
    for i:=0;i<len(mat);i++{
        for j:=0;j<len(mat[i]);j++{
            x1:=max(i-k,0)
            y1:=max(j-k,0)
            x2:=min(i+k,len(mat)-1)
            y2:=min(j+k,len(mat[i])-1)
            mat[i][j]=
            sum[x2+1][y2+1]-sum[x2+1][y1]-sum[x1][y2+1]+sum[x1][y1]
		}
	}
    return mat
}

func max (a,b int)int{
    if a>b{
		return a
	}
    return b
}
func min(a,b int)int{
    if a>b {
		return b
	}
    return a
}