Medium

题目描述

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

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

实现 NumMatrix 类：

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

你必须设计一个时间复杂度为 O(1) 的 sumRegion 算法。

示例 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
  • -10^4 <= matrix[i][j] <= 10^4
  • 0 <= row1 <= row2 < m
  • 0 <= col1 <= col2 < n
  • 最多调用 10^4 次 sumRegion 方法

解题思路

这是一个典型的二维前缀和问题。由于需要频繁查询子矩形的元素和，且要求 O(1) 时间复杂度，我们需要预处理来优化查询效率。

核心思路

二维前缀和思想：类似于一维前缀和，我们可以构建二维前缀和数组 prefixSum，其中 prefixSum[i][j] 表示从 (0,0) 到 (i-1,j-1) 矩形区域内所有元素的和。

预处理阶段：

  • 创建 (m+1) × (n+1) 的前缀和数组，多出的一行一列用于处理边界情况
  • 递推公式：prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] + matrix[i-1][j-1]
  • 这个公式基于容斥原理，避免重复计算重叠区域

查询阶段：

  • 对于查询区域 (row1, col1) 到 (row2, col2) 的和
  • 使用容斥原理：总和 = prefixSum[row2+1][col2+1] - prefixSum[row1][col2+1] - prefixSum[row2+1][col1] + prefixSum[row1][col1]

这种方法将每次查询的时间复杂度从 O(mn) 降低到 O(1)，空间复杂度为 O(mn)。

代码实现

class NumMatrix {
private:
    vector<vector<int>> prefixSum;
    
public:
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        prefixSum = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] 
                                - prefixSum[i-1][j-1] + matrix[i-1][j-1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return prefixSum[row2+1][col2+1] - prefixSum[row1][col2+1] 
               - prefixSum[row2+1][col1] + prefixSum[row1][col1];
    }
};

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), len(matrix[0])
        self.prefix_sum = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                self.prefix_sum[i][j] = (self.prefix_sum[i-1][j] + 
                                       self.prefix_sum[i][j-1] - 
                                       self.prefix_sum[i-1][j-1] + 
                                       matrix[i-1][j-1])

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return (self.prefix_sum[row2+1][col2+1] - 
                self.prefix_sum[row1][col2+1] - 
                self.prefix_sum[row2+1][col1] + 
                self.prefix_sum[row1][col1])

public class NumMatrix {
    private int[,] prefixSum;

    public NumMatrix(int[][] matrix) {
        int m = matrix.Length;
        int n = matrix[0].Length;
        prefixSum = new int[m + 1, n + 1];
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                prefixSum[i, j] = prefixSum[i-1, j] + prefixSum[i, j-1] 
                                - prefixSum[i-1, j-1] + matrix[i-1][j-1];
            }
        }
    }
    
    public int SumRegion(int row1, int col1, int row2, int col2) {
        return prefixSum[row2+1, col2+1] - prefixSum[row1, col2+1] 
               - prefixSum[row2+1, col1] + prefixSum[row1, col1];
    }
}

var NumMatrix = function(matrix) {
    const m = matrix.length;
    const n = matrix[0].length;
    this.prefixSum = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            this.prefixSum[i][j] = this.prefixSum[i-1][j] + this.prefixSum[i][j-1] 
                                 - this.prefixSum[i-1][j-1] + matrix[i-1][j-1];
        }
    }
};

NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
    return this.prefixSum[row2+1][col2+1] - this.prefixSum[row1][col2+1] 
           - this.prefixSum[row2+1][col1] + this.prefixSum[row1][col1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
初始化O(m×n)O(m×n)
sumRegionO(1)O(1)

其中 m 和 n 分别为矩阵的行数和列数。

相关题目