📘 題目敘述
給你一個 m x n 的正整數矩陣 grid。我要判斷是否存在一刀水平切割或一刀垂直切割，使得：
- 切完後的兩部分都非空
- 兩部分元素總和相等
如果可以，回傳 true；否則回傳 false。
條件限制
1 <= m == grid.length <= 10^51 <= n == grid[i].length <= 10^52 <= m * n <= 10^51 <= grid[i][j] <= 10^5
🧠 解題思路
我這題的想法很直接：
- 先算每一列的總和
- 先算每一行的總和
- 然後分別嘗試：
- 水平切一刀
- 垂直切一刀
如果是水平切，那我其實只是在看：
- 上半部列總和
- 下半部列總和
有沒有哪個切點會讓這兩個值相等。
垂直切也是完全一樣的概念，只是改成看行總和。
因為題目保證所有數字都是正數，所以前綴和只會越加越大。 因此當某一邊已經大於另一邊時，後面就不可能再相等了，這時可以直接停止。
所有變數
m：列數n：行數h：h[i]表示第i列的總和v：v[i]表示第i行的總和hsum：所有列總和加起來的值，也就是整個矩陣總和vsum：所有行總和加起來的值，也就是整個矩陣總和sum：暫時用來計算某一列或某一行的總和check：目前前綴部分的總和
🪜 主要流程步驟
1. 先算每一列的總和
我先把每一列的總和存進 h。
這樣之後如果我要試某個水平切割，就不用重新掃整個子矩陣， 只要看前面幾列的總和和後面幾列的總和即可。
這裡的 hsum 其實就是整個矩陣總和。
2. 再算每一行的總和
這一步和前面完全對稱，只是改成算每一行的總和。
這樣之後如果我要試垂直切割，就可以直接靠 v 來做前綴加總。
這裡的 vsum 也會等於整個矩陣總和。
3. 先枚舉每個可能的水平切割位置
這裡我讓：
check表示目前上半部的總和hsum表示目前下半部的總和
每次把第 k 列加到上半部後，就等於在考慮：
- 上面包含
0 ~ k列 - 下面包含
k + 1 ~ m - 1列
如果這時：
check == hsum
代表找到一個合法的水平切割，直接回傳 true。
4. 為什麼 check > hsum 時可以直接停
else if (check > hsum) {
break;
}這一點是因為題目保證矩陣元素全是正數。
所以當我繼續往下加列時：
check只會越來越大hsum只會越來越小
因此如果某一刻已經有：
check > hsum
那後面就不可能再回到相等了，可以直接停止，不用再繼續枚舉。
5. 如果水平切不到，再試垂直切割
這裡完全就是把前面的水平切邏輯，改成用行總和做一次。
現在：
check表示左半部總和vsum表示右半部總和
每次加上一整行之後，就等於在考慮某個垂直切點。
如果左右相等，就直接回傳 true。
如果左邊已經大於右邊，因為所有數字都為正，後面也不可能再相等，所以也可以直接停止。
6. 如果水平和垂直都找不到，就回傳 false
return false;如果兩種切法都試完，還是沒有任何一個切點能讓兩部分總和相等，
那答案就是 false。
⏱️ 複雜度
設 m = grid.length，n = grid[0].length。
- 時間複雜度：
O(mn + m + n)先掃整個矩陣算列總和與行總和，再各掃一次列與行前綴。 - 空間複雜度：
O(m + n)額外用了h和v兩個陣列來存每列、每行總和。
💻 程式碼實作
class Solution {
public:
bool canPartitionGrid(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<long long> h(m);
vector<long long> v(n);
long long hsum = 0, vsum = 0;
for (int i = 0; i < m; i++) {
long long sum = 0;
for (int j = 0; j < n; j++) {
sum += grid[i][j];
hsum += grid[i][j];
}
h[i] = sum;
}
for (int i = 0; i < n; i++) {
long long sum = 0;
for (int j = 0; j < m; j++) {
sum += grid[j][i];
vsum += grid[j][i];
}
v[i] = sum;
}
long long check = 0;
for (int k = 0; k < m; k++) {
check += h[k];
hsum -= h[k];
if (check == hsum) {
return true;
} else if (check > hsum) {
break;
}
}
check = 0;
for (int l = 0; l < n; l++) {
check += v[l];
vsum -= v[l];
if (check == vsum) {
return true;
} else if (check > vsum) {
break;
}
}
return false;
}
};