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

Categories:

题目描述
思路分析
1. 解法一：二维前缀和（推荐）
相似题目

题目描述

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

思路分析

解法一：二维前缀和（推荐）

核心思路：

预计算 pre[i+1][j+1] 表示左上角到 (i,j) 的矩形和。

查询时用容斥公式 O(1) 得到区域和。

初始化一次，多次查询。

复杂度分析：

时间复杂度：O(m * n) 预处理，O(1) 查询。

空间复杂度：O(m * n)，用于前缀和数组。

class NumMatrix {
    private final int[][] pre;

    public NumMatrix(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        pre = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return pre[row2 + 1][col2 + 1]
                - pre[row1][col2 + 1]
                - pre[row2 + 1][col1]
                + pre[row1][col1];
    }
}

type NumMatrix struct {
	pre [][]int
}

func Constructor(matrix [][]int) NumMatrix {
	m, n := len(matrix), len(matrix[0])
	pre := make([][]int, m+1)
	for i := range pre {
		pre[i] = make([]int, n+1)
	}

	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + matrix[i-1][j-1]
		}
	}

	return NumMatrix{pre: pre}
}

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

相似题目

题目	难度	考察点
303. 区域和检索 - 数组不可变	简单	前缀和
1314. 矩阵区域和	中等	前缀和
1074. 元素和为目标值的子矩阵数量	困难	前缀和
221. 最大正方形	中等	动态规划
304. 二维区域和检索 - 矩阵不可变	中等	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/60478616