จำนวนซับแมทริกซ์ที่มีผลรวมเท่ากับเป้าหมายใน C++

คำอธิบายปัญหา

ให้เมทริกซ์และค่าเป้าหมาย (target) เราต้องการหาจำนวนซับแมทริกซ์ที่ไม่ว่างซึ่งผลรวมขององค์ประกอบเท่ากับค่าเป้าหมาย ซับแมทริกซ์ [(x1, y1), (x2, y2)] หมายถึงเซลล์ทั้งหมด matrix[x][y] ที่ x อยู่ระหว่าง x1 ถึง x2 และ y อยู่ระหว่าง y1 ถึง y2 สองซับแมทริกซ์ถือว่าต่างกันหากมีพิกัดต่างกันแม้แต่ค่าเดียว

ตัวอย่าง

เมทริกซ์:

0 1 0
1 1 1
0 1 0

target = 0 ผลลัพธ์คือ 4 เนื่องจากมีซับแมทริกซ์ขนาด 1x1 ที่มีค่า 0 ทั้งหมด 4 ตัว

แนวทางแก้ปัญหา

1. คำนวณคำนำหน้าสะสม (prefix sum) แบบแถวสำหรับแต่ละแถว
2. วนลูปคอลัมน์เริ่มต้น i และคอลัมน์สิ้นสุด j
3. สำหรับแต่ละคู่ (i, j) คำนวณผลรวมของแต่ละแถวในช่วงคอลัมน์นั้น
4. ใช้แฮชแมปเก็บความถี่ของผลรวมสะสม เพื่อหาจำนวนซับอาร์เรย์ที่มีผลรวมเท่ากับ target

การทำงานรายละเอียด

ans := 0
col := จำนวนคอลัมน์
row := จำนวนแถว
// คำนวณ prefix sum แบบแถว
for i := 0 ถึง row-1:
    for j := 1 ถึง col-1:
        matrix[i][j] += matrix[i][j-1]

// วนลูปคอลัมน์เริ่มต้นและสิ้นสุด
for i := 0 ถึง col-1:
    for j := i ถึง col-1:
        clear map m
        m[0] := 1
        sum := 0
        for k := 0 ถึง row-1:
            current := matrix[k][j]
            if i-1 >= 0: current -= matrix[k][i-1]
            sum += current
            ans += m[target - sum]
            m[-sum]++
return ans

ตัวอย่างโค้ด 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();
        
        // Row-wise prefix sum
        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);
    return 0;
}

ความซับซ้อน

• เวลา: O(col² × row)
• พื้นที่: O(row) สำหรับแฮชแมป