Số lượng ma trận con có tổng bằng mục tiêu trong C++

Cho một ma trận và một giá trị mục tiêu, ta cần tìm số lượng ma trận con không rỗng có tổng các phần tử bằng mục tiêu. Một ma trận con [(x1, y1), (x2, y2)] là tập hợp tất cả các ô matrix[x][y] với x trong khoảng từ x1 đến x2 và y trong khoảng từ y1 đến y2. Hai ma trận con được coi là khác nhau nếu có ít nhất một tọa độ khác nhau.

Ví dụ, với ma trận:

và target = 0, kết quả sẽ là 4, tương ứng với bốn ma trận con 1x1 chỉ chứa giá trị 0.

Giải thuật

1. Khởi tạo ans = 0.
2. Tính số cột (col) và số hàng (row).
3. Tính tổng tiền tố theo hàng: với mỗi hàng i, duyệt cột j từ 1 đến col-1, cập nhật matrix[i][j] += matrix[i][j-1].
4. Duyệt qua tất cả các cặp cột (i, j) với i ≤ j:
   • Khởi tạo map m, đặt m[0] = 1, sum = 0.
   • Duyệt qua từng hàng k:
     • Tính current = matrix[k][j] - (i > 0 ? matrix[k][i-1] : 0).
     • Cập nhật sum += current.
     • Cộng vào ans giá trị m[target - sum] (nếu có).
     • Tăng m[-sum] lên 1.
5. Trả về ans.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int ans = 0;
        int col = matrix[0].size();
        int row = matrix.size();
        for(int i = 0; i < row; i++){
            for(int j = 1; j < col; j++){
                matrix[i][j] += matrix[i][j - 1];
            }
        }
        unordered_map<int, int> m;
        for(int i = 0; i < col; i++){
            for(int j = i; j < col; j++){
                m.clear();
                m[0] = 1;
                int sum = 0;
                for(int k = 0; k < row; k++){
                    int current = matrix[k][j];
                    if(i - 1 >= 0) current -= matrix[k][i - 1];
                    sum += current;
                    ans += m[target - sum];
                    m[-sum]++;
                }
            }
        }
        return ans;
    }
};
int main(){
    Solution ob;
    vector<vector<int>> v = {{0,1,0},{1,1,1},{0,1,0}};
    cout << (ob.numSubmatrixSumTarget(v, 0));
}

Đầu vào

{{0,1,0},{1,1,1},{0,1,0}}, 0

Đầu ra

4