LeetCode 第304题：二维区域和检索 - 矩阵不可变

📖 文章摘要

本文详细解析LeetCode第304题“二维区域和检索 - 矩阵不可变”，这是一道考察二维前缀和的中等难度题目。文章提供了暴力求和和二维前缀和两种实现方案，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合学习二维前缀和和矩阵处理的读者。

核心知识点： 二维前缀和、矩阵处理、查询优化
难度等级： 中等
推荐人群： 具备基础算法知识，想要提升矩阵处理和查询优化能力的开发者

题目描述

给定一个二维矩阵 matrix，以下类型的多个请求：

计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。

实现 NumMatrix 类：

NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
int sumRegion(int row1, int col1, int row2, int col2) 返回左上角 (row1, col1) 、右下角 (row2, col2) 的子矩阵的元素总和。

示例

示例 1：

输入：
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出：
[null,8,11,12]

解释：
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

示例矩阵和查询区域

提示

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
-105 <= matrix[i][j] <= 105
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
最多调用 104 次 sumRegion 方法

解题思路

本题可以使用两种方法来实现：

暴力求和法：
- 每次查询时遍历子矩阵求和
- 不需要额外空间
- 查询时间复杂度O(mn)
- 适合查询次数少的情况
二维前缀和法：
- 预处理计算二维前缀和数组
- 利用容斥原理快速计算子矩阵和
- 查询时间复杂度O(1)
- 适合频繁查询的情况

图解思路

二维前缀和计算表

位置	计算公式	含义
preSum[i][j]	preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1]	(0,0)到(i-1,j-1)的矩形和
查询结果	preSum[row2+1][col2+1] - preSum[row2+1][col1] - preSum[row1][col2+1] + preSum[row1][col1]	子矩阵元素和

容斥原理示意表

区域	操作	说明
大矩形	+	包含目标区域的最大前缀和
上方矩形	-	减去上方多余区域
左方矩形	-	减去左方多余区域
左上重叠	+	补回重复减去的区域

代码实现

C# 实现

public class NumMatrix {
    private int[,] preSum;
    
    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.Length == 0 || matrix[0].Length == 0) return;
        
        int m = matrix.Length;
        int n = matrix[0].Length;
        preSum = new int[m + 1, n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                preSum[i,j] = preSum[i-1,j] + preSum[i,j-1] - preSum[i-1,j-1] + matrix[i-1][j-1];
            }
        }
    }
    
    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];
    }
}

Python 实现

class NumMatrix:
    def __init__(self, matrix: List[List[int]]):
        if not matrix or not matrix[0]:
            return
            
        m, n = len(matrix), len(matrix[0])
        self.preSum = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                self.preSum[i][j] = (self.preSum[i-1][j] + 
                                   self.preSum[i][j-1] - 
                                   self.preSum[i-1][j-1] + 
                                   matrix[i-1][j-1])
    
    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return (self.preSum[row2+1][col2+1] - 
                self.preSum[row2+1][col1] - 
                self.preSum[row1][col2+1] + 
                self.preSum[row1][col1])

C++ 实现

class NumMatrix {
private:
    vector<vector<int>> preSum;
    
public:
    NumMatrix(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        
        int m = matrix.size();
        int n = matrix[0].size();
        preSum = vector<vector<int>>(m + 1, vector<int>(n + 1));
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                preSum[i][j] = preSum[i-1][j] + 
                              preSum[i][j-1] - 
                              preSum[i-1][j-1] + 
                              matrix[i-1][j-1];
            }
        }
    }
    
    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];
    }
};

执行结果

C# 实现

执行用时：156 ms
内存消耗：65.8 MB

Python 实现

执行用时：108 ms
内存消耗：17.2 MB

C++ 实现

执行用时：24 ms
内存消耗：15.1 MB

性能对比

语言	执行用时	内存消耗	特点
C#	156 ms	65.8 MB	实现简单，内存占用大
Python	108 ms	17.2 MB	代码简洁，性能适中
C++	24 ms	15.1 MB	性能最优，内存占用小

代码亮点

🎯 使用二维前缀和优化查询效率
💡 巧妙应用容斥原理
🔍 优化边界条件处理
🎨 代码结构清晰，易于维护

常见错误分析

🚫 前缀和数组大小错误
🚫 边界索引计算错误
🚫 未考虑空矩阵情况
🚫 容斥原理应用错误

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
暴力求和	O(mn)	O(1)	空间占用小	查询慢
二维前缀和	O(1)	O(mn)	查询快	需要额外空间

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第304题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

提示

解题思路

图解思路

二维前缀和计算表

容斥原理示意表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流