leetcode3546. 等和矩阵分割 I- medium

1 题目：等和矩阵分割 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\ast n<=10^5$
$1<=grid[i][j]<=10^5$

2 solution

可以求每一行每一列，以及整个矩阵的和 S， 如果行某一的前缀和或者列的某一前缀和等于 S/2 即可分割。

代码

class Solution {
public:bool canPartitionGrid(vector<vector<int>> &grid) {int m = grid.size(), n = grid[0].size();vector<long long> cols(n + 1), rows(m + 1);long long s = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {cols[j + 1] += grid[i][j];rows[i + 1] += grid[i][j];s += grid[i][j];}}if(s & 1) return false;s /= 2;for (int i = 1; i <= m; i++) {rows[i] += rows[i - 1];if(rows[i] == s) return true;if(rows[i] > s) break;}for (int i = 1; i <= n; i++) {cols[i] += cols[i - 1];if(cols[i] == s) return true;if(cols[i] > s) break;}return false;}
};

结果