前言

保持前缀和对连续子数组的敏感性，才能快速转换问题，做到举一反三。
如前缀和能拿来求矩阵和，根据矩阵特性，可以将一维前缀和变为二维前缀和。

一、案例

二、题解

1）一维前缀和，用空间换时间，将暴力的时间复杂度O(M x N)降到O(M);
2）二维前缀和，进一步用空间换时间，将一维前缀和的时间复杂度O(M)降到O(1);

package com.xhu.offer.offerII;import java.util.Arrays;
import java.util.Map;//二维子矩阵的和
public class NumMatrix {//前缀和，用空间换时间，将暴力O(MxN)降到O(M)private int[][] prefix;public NumMatrix(int[][] matrix) {int m = matrix.length, n = matrix[0].length;prefix = new int[m][n];for (int i = 0; i < m; i++) {int prefixSum = 0;for (int j = 0; j < n; j++) prefix[i][j] = (prefixSum += matrix[i][j]);}}public int sumRegion(int row1, int col1, int row2, int col2) {int res = 0;for (int i = row1; i <= row2; i++) res += col1 == 0 ? prefix[i][col2] : prefix[i][col2] - prefix[i][col1 - 1];return res;}
}//采用二维前缀和来以O(1)的时间求和
class NumMatrix2 {//前缀和，用空间换时间，将暴力O(MxN)降到O(M)private int[][] prefix;public NumMatrix2(int[][] matrix) {int m = matrix.length, n = matrix[0].length;prefix = new int[m][n];for (int i = m - 1; i >= 0; i--) {for (int j = n - 1; j >= 0; j--) {int right = j + 1 == n ? 0 : prefix[i][j + 1];int down = i + 1 == m ? 0 : prefix[i + 1][j];int surplus = j + 1 < n && i + 1 < m ? prefix[i + 1][j + 1] : 0;prefix[i][j] =matrix[i][j] +  right + down - surplus;}}}public int sumRegion(int row1, int col1, int row2, int col2) {int m = prefix.length, n = prefix[0].length;int main = prefix[row1][col1];int right = col2 + 1 == n ? 0 : prefix[row1][col2 + 1];int down = row2 + 1 == m ? 0 : prefix[row2 + 1][col1];int surplus = col2 + 1 < n && row2 + 1 < m ? prefix[row2 + 1][col2 + 1] : 0;return main - right - down + surplus;}
}

总结

1）空间换时间
2）如以前总结所示，保持前缀和对连续子数组的敏感性，才能促进问题转换，举一反三。

参考文献

[1] LeetCode 原题