leetcode筆記：Range Sum Query 2D

一. 題目描述

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPjxzdHJvbmc+tv4uIMzixL+31s72PC9zdHJvbmc+PC9wPg0KPHA+zOLEv7Tz0uLKx6OsuPi2qNK7uPa2/s6svtjV86OsvMbL47TTz8Kx6jxjb2RlPihyb3cxLCBjb2wxKTwvY29kZT4gtb3PwrHqo7ogPGNvZGU+KHJvdzIsIGNvbDIpPC9jb2RlPrXE19O+2NXztcS6zaGjzOLEv7j4s/bBy7y4uPay4srU08PA/aGjPC9wPg0KPHA+16LS4srCz+7W0Mzhtb2jujwvcD4NCrzZyei+2NXzsru74bjEseSjuyBzdW1SZWdpb26jqLLp0a+jqbqvyv274bX308O63LbgtM6juyC82cnoPGNvZGU+cm93MSAmbGU7IHJvdzI8L2NvZGU+o6wgsqLH0iA8Y29kZT5jb2wxICZsZTsgY29sMjwvY29kZT6how0KPHA+uMPM4rXE1ti148rHyrm1sbbgtM6199PDc3VtUmVnaW9uuq/K/cqxo6zL47eoxNyxo7PWuN/Qp6Os0vK0y9fu1rG527XEt723qMrHyrnTw7/VvOS7u8ihyrG85KOszai5/bm51Oy4qNb6yv3X6Txjb2RlPnN1bVJlY29yZDwvY29kZT6jrDxjb2RlPnN1bVJlY29yZFtpXVtqXTwvY29kZT6x7cq+tNPPwrHqPGNvZGU+KDAsIDApPC9jb2RlPrW9PGNvZGU+KHgsIHkpPC9jb2RlPrXE19O+2NXztcS6zaOov7zCx7W9sd+9587KzOKjrLio1vrK/dfpPGNvZGU+c3VtUmVjb3JkPC9jb2RlPrTz0KHJ6M6qPGNvZGU+KG0gKyAxKSAqIChuICsgMSk8L2NvZGU+o6zG5NbQPGNvZGU+bTwvY29kZT66zTxjb2RlPm48L2NvZGU+t9ax8M6qyv3X6Txjb2RlPm1hdHJpeDwvY29kZT61xNDQyv26zcHQyv2jqaOsyrm1w8zixL/XqruvzqrH88ihvtjQzrHfvee1xM7KzOKjrMjnz8LD5sv5yr6hozwvcD4NCjxwPsO709DK1ravu63NvKOs0v3Tw834yc+1xM+1wdDNvMasvfjQ0L3iys2jujwvcD4NCjxwcmUgY2xhc3M9"brush:java;"> +-----+-+-------+ +--------+-----+ +-----+---------+ +-----+--------+ | | | | | | | | | | | | | | | | | | | | | | | | | | +-----+-+ | +--------+ | | | | +-----+ | | | | | = | | + | | | - | | +-----+-+ | | | +-----+ | | | | | | | | | | | | | | | | | | | +---------------+ +--------------+ +---------------+ +--------------+ sumRecord[i][j] = sumRecord[i-1][j] + sumRecord[i][j-1] - sumRecord[i-1][j-1] + matrix[i-1][j-1]

這是小學學過的簡單的矩形求面積方法，對於本題正好適用。

三. 示例代碼

class NumMatrix {
public:
    NumMatrix(vector> &matrix) {
        int m = matrix.size();
        int n = m > 0 ? matrix[0].size() : 0;
        sumRecord = vector>(m + 1, vector(n + 1, 0));
        // 由於sumRegion函數可能被調用多次，因此使用輔助數組sumRecord用於
        // 記錄matrix中坐標(0,0)到任一下標(i,j)之間矩形框內元素的值，這樣
        // 每次調用sumRegion函數時只需查詢sumRecord裡的值並進行簡單運算即可
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                sumRecord[i][j] = matrix[i - 1][j - 1] + sumRecord[i - 1][j] + sumRecord[i][j - 1] - sumRecord[i - 1][j - 1];
    }

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

private:
    vector> sumRecord;
};


// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);

四. 小結

在構造輔助數組時，應考慮邊界問題和下標的轉換，否則容易出現越界等錯誤。