Share my c++ solution using the sum to (0, 0)


  • 0
    O
    class NumMatrix {
        vector<vector<int> > v;
    public:
        NumMatrix(vector<vector<int>> &matrix) {
            int N = matrix.size();
            if (N <= 0) return;
            int M = matrix[0].size();
            v.push_back(vector<int> (M + 2, 0));
            for (int i = 0; i < N; i++) {
                vector<int> tmp = matrix[i];
                tmp.insert(tmp.begin(), 0);
                tmp.push_back(0);
                v.push_back(tmp);
            }
            for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) {
                v[i][j] += v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1];
            }
        }
    
        int sumRegion(int row1, int col1, int row2, int col2) {
            return v[row2 + 1][col2 + 1] - v[row1][col2 + 1] - v[row2 + 1][col1] + v[row1][col1];
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.