M3546.等和矩阵分割 I

matrix, https://leetcode.cn/problems/equal-sum-grid-partition-i/

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

python

from typing import List

class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        total_sum = sum(sum(row) for row in grid)

        # 如果总和是奇数，不可能均分
        if total_sum % 2 != 0:
            return False

        target = total_sum // 2

        # 尝试水平分割：按行求和并检查是否存在中间行使得前 k 行的和为 target
        row_sum = 0
        for i in range(m - 1):  # 至少保留一行给下面部分
            row_sum += sum(grid[i])
            if row_sum == target:
                return True

        # 尝试垂直分割：按列求和并检查是否存在中间列使得前 k 列的和为 target
        col_sum = [0] * n
        for j in range(n):
            for i in range(m):
                col_sum[j] += grid[i][j]
        vertical_prefix = 0
        for j in range(n - 1):  # 至少保留一列给右边部分
            vertical_prefix += col_sum[j]
            if vertical_prefix == target:
                return True

        return False

M3546.等和矩阵分割 I ​

M3546.等和矩阵分割 I