303. 区域和检索 - 数组不变

想法：

  1. 直接循环计算从i 到 j 两个区域中的所有数值和。但是由于每次检索都需要计算一遍，这样会造成多次计算已有的数值。
  2. 注意到当 i≤j 时，sumRange(i,j) 可以写为如下形式： sumRange(i,j) = 到下标j所有数值和 - 到i-1下标所有数值和。 假设数组 nums 的长度为 n，创建长度为 n+1 的前缀和数组 sums，对于 0≤i<n 都有 sums[i+1] = sums[i]+nums[i]，则当 0<i≤n时，sums[i] 表示数组nums 从下标 0到下标 i-1 的前缀和。

​ 因此可以得出： sumRange(i,j) = sums[j+1] - sums[i]

编码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class NumArray {
public:
    vector<int> sums;

    NumArray(vector<int>& nums) {
        int n = nums.size();
        sums.resize(n + 1);
        for (int i = 0; i < n; i++) {
            sums[i + 1] = sums[i] + nums[i];
        }
    }

    int sumRange(int i, int j) {
        return sums[j + 1] - sums[i];
    }
};

时间复杂度：初始化需要计算nums 的前缀和，因此时间复杂度为 O(n)

空间复杂度：需要创建一个大小为 n+1 的前缀和数组 sums，因此空间复杂度为 O(n)

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

想法：

  1. 此题将数组扩展到了二维，如果采用一位前缀和的方式。假设 f(i,j) 为从matrix[0][0]到matrix[i][j]的所有数值和。可以将 sumRegion 看成多个一维数组(每一行当成一个一维数组)，采用一维数组的前缀和计算方式计算区域和。

  2. 还可以考虑使用二维数组前缀和计算方式。

    计算前缀和：

​ f(i,j) = f(i-1,j) + f(i,j-1) - f(i-1,j-1) + matrix[i][j]

​

​ 计算区域和：

编码：

  • 一维前缀和解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class NumMatrix {
public:
    vector<vector<int>> sums;

    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if (m > 0) {
            int n = matrix[0].size();
            sums.resize(m, vector<int>(n + 1));
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    sums[i][j + 1] = sums[i][j] + matrix[i][j];
                }
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int i = row1; i <= row2; i++) {
            sum += sums[i][col2 + 1] - sums[i][col1];
        }
        return sum;
    }
};
  • 二维前缀和解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class NumMatrix {
public:
    vector<vector<int>> sums;

    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        if (m > 0) {
            int n = matrix[0].size();
            sums.resize(m + 1, vector<int>(n + 1));
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    sums[i + 1][j + 1] = sums[i][j + 1] + sums[i + 1][j] - sums[i][j] + matrix[i][j];
                }
            }
        }
    }

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

参考文章：

https://leetcode-cn.com/problems/range-sum-query-2d-immutable/solution/er-wei-qu-yu-he-jian-suo-ju-zhen-bu-ke-b-2z5n/