M3546.等和矩阵分割 I

brute force, prefix sum, 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

这是一个经典的矩阵前缀和问题。题目要求判断是否能通过一条水平线或一条垂直线将矩阵分为两个和相等的部分。

解题思路

计算总和：首先遍历整个矩阵，计算所有元素的总和 $S$ 。如果 $S$ 是奇数，显然无法平分成两个整数部分，直接返回 false。
目标值：我们的目标是找到一个分割点，使得其中一部分的和等于 $t a r g e t = S / 2$ 。
水平分割：
- 逐行累加每一行的元素总和。
- 由于分割出的两个部分必须非空，我们检查从第 $0$ 行到第 $m - 2$ 行（ $m$ 为总行数）。
- 如果在某一时刻累加和等于 $t a r g e t$ ，说明存在水平分割线，返回 true。
垂直分割：
- 逐列累加每一列的元素总和。
- 由于分割出的两个部分必须非空，我们检查从第 $0$ 列到第 $n - 2$ 列（ $n$ 为总列数）。
- 如果在某一时刻累加和等于 $t a r g e t$ ，说明存在垂直分割线，返回 true。
复杂度分析：
- 时间复杂度： $O (m \times n)$ 。我们需要遍历矩阵来计算总和及列和，其中 $m \times n$ 最大为 $10^{5}$ 。
- 空间复杂度： $O (m + n)$ 。用于存储每一行或每一列的和。
代码实现

python

from typing import List

class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        m = len(grid)
        n = len(grid[0])
        
        # 1. 计算每一行的和以及总和
        row_sums = [sum(row) for row in grid]
        total_sum = sum(row_sums)
        
        # 如果总和是奇数，不可能平分
        if total_sum % 2 != 0:
            return False
        
        target = total_sum // 2
        
        # 2. 尝试水平分割
        # 分割线可以在第 0 行到第 m-2 行之后（保证两部分非空）
        current_row_sum = 0
        for i in range(m - 1):
            current_row_sum += row_sums[i]
            if current_row_sum == target:
                return True
        
        # 3. 尝试垂直分割
        # 计算每一列的和
        col_sums = [0] * n
        for r in range(m):
            for c in range(n):
                col_sums[c] += grid[r][c]
        
        # 分割线可以在第 0 列到第 n-2 列之后
        current_col_sum = 0
        for j in range(n - 1):
            current_col_sum += col_sums[j]
            if current_col_sum == target:
                return True
        
        return False

关键点总结

非空约束：代码中 range(m - 1) 和 range(n - 1) 确保了分割后至少留下一行或一列，满足“非空”条件。
效率：虽然矩阵可能很大（ $10^{5}$ 级），但总元素个数 $m \times n$ 限制在 $10^{5}$ 以内，因此 $O (m \times n)$ 的算法完全可以胜任。
内存安全：在 Python 中，sum(row) 和列遍历都是标准的线性操作。

M3546.等和矩阵分割 I ​

M3546.等和矩阵分割 I