题目

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

解题思路

1. 计算矩阵总和 (Total Sum)

首先遍历整个矩阵，计算所有元素的总和 $S$。

关键点：如果总和 $S$ 是奇数，那么它不可能被平分为两个相等的整数部分，直接返回 false。
目标值：我们需要寻找的部分和目标值就是 $Target = S / 2$。

2. 水平分割尝试 (Horizontal Split)

水平分割意味着我们在第 $i$ 行和第 $i+1$ 行之间切一刀。

计算每一行的行总和。
从第一行开始向下累加这些行总和（即计算行方向的前缀和）。
判定条件：在累加到第 $m-1$ 行之前（必须留出至少一行作为第二部分），如果当前累加和等于 $Target$，则说明找到了合法的水平分割线，返回 true。

3. 垂直分割尝试 (Vertical Split)

如果水平分割没找到，我们就尝试在第 $j$ 列和第 $j+1$ 列之间切一刀。

计算每一列的列总和。
从第一列开始向右累加这些列总和（即计算列方向的前缀和）。
判定条件：在累加到第 $n-1$ 列之前（必须留出至少一列作为第二部分），如果当前累加和等于 $Target$，则说明找到了合法的垂直分割线，返回 true。

4. 最终结果

如果遍历完所有的水平和垂直可能性都没有找到满足条件的切分点，则返回 false。

复杂度分析

时间复杂度：$O(m \times n)$。我们需要遍历一遍矩阵来计算总和，以及计算行/列的和。对于 $10^5$ 级别的数据量，这个复杂度是完全可以接受的。
空间复杂度：$O(m + n)$。我们需要额外的空间来存储每一行和每一列的和。

具体代码

func canPartitionGrid(grid [][]int) bool {

    m := len(grid)
    n := len(grid[0])
    total_sum := 0

    row_vec := make([]int, m)
    col_vec := make([]int, n)

    for i := range m {
        row_sum := 0
        for j := range n {
            total_sum += grid[i][j]
            row_sum += grid[i][j]
        }
        row_vec[i] = row_sum
    }

    if total_sum % 2 == 1 {
        return false
    } else {
        total_sum /= 2
    }

    for j := range n {
        col_sum := 0
        for i := range m {
            col_sum += grid[i][j]
        }
        col_vec[j] = col_sum
    }


    row_sum := 0
    col_sum := 0
    for k := range max(n, m) {

        if k < m {
            row_sum += row_vec[k]
            if row_sum == total_sum {
                return true
            }
        }

        if k < n {
            col_sum += col_vec[k]
            if col_sum == total_sum {
                return true
            }
        }
    }

    return false
    
}

beautifulremi / 3546. 等和矩阵分割 I

题目