Sword finger offer II 013 Sum of two dimensional submatrix

summary

Look at my picture , It is clear at a glance .

subject

link ：https://leetcode.cn/problems/O4NDxx

Given a two-dimensional matrix matrix, Multiple requests of the following types ：

• Calculate the sum of the elements in its subrectangle , The upper left corner of the submatrix is (row1, col1) , The lower right corner is (row2, col2) .

Realization NumMatrix class ：

• NumMatrix(int[][] matrix) Given an integer matrix matrix To initialize
• int sumRegion(int row1, int col1, int row2, int col2) Return to the upper left corner (row1, col1) 、 The lower right corner (row2, col2) The sum of the elements of the submatrix of .

Ideas

At first glance , The question is confused , Later, I found that his input and output were written in a mess .

The easiest way , It is based on the incoming row and column coordinates , The sum of the corresponding submatrix is traversed row by row .

Solution 1 ： Regular traversal

Code

int[][] matrix;

public NumMatrix(int[][] matrix) {
    this.matrix = matrix;
}

public int sumRegion(int row1, int col1, int row2, int col2) {
    int result = 0;
    for (int i = row1; i <= row2; i++) {
        int[] matrix = this.matrix[i];
        for (int j = col1; j <= col2; j++) {
            result += matrix[j];
        }
    }
    return result;
}

Solution 2 ： Preprocessing matrix

Logic

Let's further optimize , Think about it , Can we follow the previous questions , By adding and the difference between them , Directly calculate the sum of submatrix ？

Look at the picture and find the pattern ：

If we want to sum the blue submatrix , Then use the sum of the whole matrix - Sum of red frame submatrix - Sum of yellow frame submatrix + Sum of green submatrix , That's all right. .

So when we preprocess the matrix , You just need to traverse and calculate (0,0) To the sum of the area of the submatrix formed between each element , It can be used in the final calculation .

Be careful , Here, when dealing with , It is handled line by line .

Code

int[][] sumMatrix;
public NumMatrix(int[][] matrix) {
    
  int[][] sumMatrix = new int[matrix.length + 1][matrix[0].length + 1];
  for (int i = 0; i < matrix.length; i++) {
    
    int rowSum = 0;
    for (int j = 0; j < matrix[0].length; j++) {
    
      rowSum += matrix[i][j];
      sumMatrix[i + 1][j + 1] = sumMatrix[i][j + 1] + rowSum;
    }
  }

  this.sumMatrix = sumMatrix;
}

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