目标
给你一个由正整数组成的 m x n 矩阵 grid。你的任务是判断是否可以通过 一条水平或一条垂直分割线 将矩阵分割成两部分，使得：
- 分割后形成的每个部分都是 非空 的。
- 两个部分中所有元素的和 相等 。
如果存在这样的分割，返回 true；否则，返回 false。
示例 1：
输入： grid = [[1,4],[2,3]]
输出： true
解释：
在第 0 行和第 1 行之间进行水平分割，得到两个非空部分，每部分的元素之和为 5。因此，答案是 true。示例 2：
输入： grid = [[1,3],[2,4]]
输出： false
解释：
无论是水平分割还是垂直分割，都无法使两个非空部分的元素之和相等。因此，答案是 false。说明：
- 1 <= m == grid.length <= 10^5
- 1 <= n == grid[i].length <= 10^5
- 2 <= m * n <= 10^5
- 1 <= grid[i][j] <= 10^5
思路
有一个 m x n 矩阵，判断能否用一条水平线或者垂直线将矩阵分割成两部分，使得两部分的和相等，并且每一部分非空。
先求出总和，根据题意枚举所有分割水平线与垂直线判断两部分的和是否相等。
代码
/**
* @date 2026-03-25 9:03
*/
public class CanPartitionGrid3546 {
public boolean canPartitionGrid(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
long sum = 0L;
for (int[] row : grid) {
for (int num : row) {
sum += num;
}
}
if (sum % 2 == 1) {
return false;
}
long half = sum / 2;
long prefix = 0L;
for (int i = 0; i < m - 1; i++) {
for (int num : grid[i]) {
prefix += num;
}
if (prefix << 1 == sum) {
return true;
} else if (prefix > half) {
break;
}
}
prefix = 0L;
for (int j = 0; j < n - 1; j++) {
for (int i = 0; i < m; i++) {
prefix += grid[i][j];
}
if (prefix << 1 == sum) {
return true;
} else if (prefix > half) {
break;
}
}
return false;
}
}
性能
