LeetCode 304 Range Sum Query 2D - Immutable

标签: 数组类题目 LeetCode 发布于:2022-02-12 14:48:58 编辑于:2022-02-12 15:48:48 浏览量:396

概述

https://leetcode.com/problems/range-sum-query-2d-immutable/

暴力遍历法

不赘述,每次查询 O(n^2) 的时间复杂度,n 为区域长宽。

前缀和

与一维情况下一样的套路。

初始化 O(n^2),每次查询 O(1)。

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

未经允许,禁止转载,本文源站链接:https://iamazing.cn/