日期: 2026年3月25日

目标

给你一个由正整数组成的 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;
    }

}

性能