3546. 等和矩阵分割 I 

English Version

题目描述

给你一个由正整数组成的 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⁵
1 <= n == grid[i].length <= 10⁵
2 <= m * n <= 10⁵
1 <= grid[i][j] <= 10⁵

解法

方法一：枚举 + 前缀和

我们先计算矩阵中所有元素的和，记为 $s$。如果 $s$ 是奇数，则不可能将矩阵分割成两个和相等的部分，直接返回 false。

如果 $s$ 是偶数，我们可以枚举所有可能的分割线，判断是否存在一条分割线将矩阵分割成两个和相等的部分。

我们从上到下遍历每一行，计算当前行之前所有行的元素之和 $\textit{pre}$，如果 $\textit{pre} \times 2 = s$，且当前行不是最后一行，则说明可以在当前行和下一行之间进行水平分割，返回 true。

如果没有找到这样的分割线，我们再从左到右遍历每一列，计算当前列之前所有列的元素之和 $\textit{pre}$，如果 $\textit{pre} \times 2 = s$，且当前列不是最后一列，则说明可以在当前列和下一列之间进行垂直分割，返回 true。

如果没有找到这样的分割线，则返回 false。

时间复杂度 $O(m \times n)$，其中 $m$ 和 $n$ 分别是矩阵的行数和列数。空间复杂度 $O(1)$，只使用了常数级别的额外空间。

Python3

class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        s = sum(sum(row) for row in grid)
        if s % 2:
            return False
        pre = 0
        for i, row in enumerate(grid):
            pre += sum(row)
            if pre * 2 == s and i != len(grid) - 1:
                return True
        pre = 0
        for j, col in enumerate(zip(*grid)):
            pre += sum(col)
            if pre * 2 == s and j != len(grid[0]) - 1:
                return True
        return False

Java

class Solution {
    public boolean canPartitionGrid(int[][] grid) {
        long s = 0;
        for (var row : grid) {
            for (int x : row) {
                s += x;
            }
        }
        if (s % 2 != 0) {
            return false;
        }
        int m = grid.length, n = grid[0].length;
        long pre = 0;
        for (int i = 0; i < m; ++i) {
            for (int x : grid[i]) {
                pre += x;
            }
            if (pre * 2 == s && i < m - 1) {
                return true;
            }
        }
        pre = 0;
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < m; ++i) {
                pre += grid[i][j];
            }
            if (pre * 2 == s && j < n - 1) {
                return true;
            }
        }
        return false;
    }
}

C++

class Solution {
public:
    bool canPartitionGrid(vector<vector<int>>& grid) {
        long long s = 0;
        for (const auto& row : grid) {
            for (int x : row) {
                s += x;
            }
        }
        if (s % 2 != 0) {
            return false;
        }
        int m = grid.size(), n = grid[0].size();
        long long pre = 0;
        for (int i = 0; i < m; ++i) {
            for (int x : grid[i]) {
                pre += x;
            }
            if (pre * 2 == s && i + 1 < m) {
                return true;
            }
        }
        pre = 0;
        for (int j = 0; j < n; ++j) {
            for (int i = 0; i < m; ++i) {
                pre += grid[i][j];
            }
            if (pre * 2 == s && j + 1 < n) {
                return true;
            }
        }
        return false;
    }
};

Go

func canPartitionGrid(grid [][]int) bool {
	s := 0
	for _, row := range grid {
		for _, x := range row {
			s += x
		}
	}
	if s%2 != 0 {
		return false
	}
	m, n := len(grid), len(grid[0])
	pre := 0
	for i, row := range grid {
		for _, x := range row {
			pre += x
		}
		if pre*2 == s && i+1 < m {
			return true
		}
	}
	pre = 0
	for j := 0; j < n; j++ {
		for i := 0; i < m; i++ {
			pre += grid[i][j]
		}
		if pre*2 == s && j+1 < n {
			return true
		}
	}
	return false
}

TypeScript

function canPartitionGrid(grid: number[][]): boolean {
    let s = 0;
    for (const row of grid) {
        s += row.reduce((a, b) => a + b, 0);
    }
    if (s % 2 !== 0) {
        return false;
    }
    const [m, n] = [grid.length, grid[0].length];
    let pre = 0;
    for (let i = 0; i < m; ++i) {
        pre += grid[i].reduce((a, b) => a + b, 0);
        if (pre * 2 === s && i + 1 < m) {
            return true;
        }
    }
    pre = 0;
    for (let j = 0; j < n; ++j) {
        for (let i = 0; i < m; ++i) {
            pre += grid[i][j];
        }
        if (pre * 2 === s && j + 1 < n) {
            return true;
        }
    }
    return false;
}