1074. Number of Submatrices That Sum to Target

題目描述

給定一個 m × n 整數矩陣 matrix 和整數 target，回傳元素總和等於 target 的非空子矩陣的數目。

子矩陣是由矩陣中一些連續的行和列所定義的矩形區域。

範例：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0

• 僅包含 [0] 的子矩陣共 4 個 → 答案 4

解題思路

核心思路：固定上下行 + 1D 前綴和 HashMap

直接枚舉所有子矩陣有四個維度（上下行 r1,r2，左右列 c1,c2），時間 O(m²n²) 過慢。

降維策略：

1. 枚舉所有上行 r1 和下行 r2（共 O(m²) 種組合）。
2. 對於固定的 r1, r2，對每一列 c，計算「r1 到 r2 行、第 c 列所有元素的和」→ 構成一個長度為 n 的一維陣列 colSum。
3. 在這個一維陣列上，用前綴和 + HashMap 求「子陣列和等於 target 的個數」（LC 560 的技巧），O(n) 完成。

總時間複雜度：O(m² × n)。

關鍵實作細節

• 為了高效計算 colSum[c]（行 r1 到 r2、列 c 的和），預先建立每行的列前綴和 rowPrefix[r][c]，使得 colSum[c] 可以 O(1) 計算。
• 或者，在枚舉 r2 時，維護滾動的 colSum[c]：固定 r1，每增加一行 r2 就把 matrix[r2][c] 加到 colSum[c]，避免重複計算。
• 對 1D 陣列 colSum 使用前綴和 + HashMap：count[prefix_sum - target] 給出以當前位置結尾的合法子陣列數。

時間複雜度

O(m² × n)，其中 m 為行數，n 為列數。

• 枚舉上下行組合：O(m²) 種。
• 對每個 (r1, r2) 組合，更新 colSum 並做一維 HashMap 掃描：O(n)。
• 總計：O(m² × n)。

若 m >> n，可以轉置矩陣，時間變為 O(n² × m)，取 min(m, n) 作為固定維度可以略微優化。

空間複雜度

O(n)，需要 colSum 陣列（長度 n）和 count HashMap（最多 n+1 個不同前綴和）。不計輸入矩陣本身。

替代方案

方案一：暴力枚舉（四重迴圈）

枚舉所有 (r1, c1, r2, c2) 四元組，用二維前綴和 O(1) 計算子矩陣和，判斷是否等於 target。

• 優點：思路最直觀，實作簡單。
• 缺點：時間 O(m²n²)，m=n=100 時約 10^8 操作，可能勉強通過但效率低；不如 O(m²n) 解法。

方案二：固定左右列 + 行前綴和

對稱地，枚舉左列 c1 和右列 c2（O(n²) 組合），對每個組合計算「每行的列和」構成一維陣列，然後用 HashMap 求子陣列和等於 target 的個數（O(m)）。總時間 O(n² × m)。

• 優點：與主要解法完全對稱，若 n < m 則更快。
• 缺點：當 m < n 時，不如固定上下行（O(m² × n) < O(n² × m)）。實際上兩者選小的維度固定即可。

方案三：隨機化或剪枝

在行列方向都不均勻的情況下（如極端瘦長矩陣），可以自適應地選擇固定哪個維度，但這是工程優化，算法本質不變。

延伸問題

1. 子矩陣和等於 target 的最小面積：在所有和等於 target 的子矩陣中，找面積最小的一個。在固定 r1, r2 後對 1D 陣列求最短子陣列和等於 target，但 1D 版本若含負數無法用滑窗，需用 HashMap + 排序前綴和，整體更複雜。

2. 最大子矩陣和：不限制等於 target，找和最大的子矩陣。固定 r1, r2 後，對 colSum 陣列用 Kadane's Algorithm O(n) 求最大子陣列和，總時間 O(m² × n)，是最大子矩陣和問題的標準解法。

3. 推廣到三維張量：若問題推廣到三維（高 × 行 × 列），固定高度範圍（O(h²)），再固定行範圍（O(m²)），最後對 1D 陣列用 HashMap（O(n)），總時間 O(h²m²n)。維度每增加一層，複雜度就多一個平方因子，實際可行性急劇下降。