3546.等和矩阵分割 I：记总记当前（遍历）

【LetMeFly】3546.等和矩阵分割 I：记总记当前（遍历）

力扣题目链接：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 <= 105
• 1 <= n == grid[i].length <= 105
• 2 <= m * n <= 105
• 1 <= grid[i][j] <= 105

 

解题方法：三次遍历

第一次遍历计算整个grid的元素之和，若非偶数直接返回false，若为偶数则直接除以$2$。

接着从上往下遍历grid，每次累加一整行的元素，若恰好等于除以二后的总和则返回true，大于则break。

最后从左往右遍历，方法和从上往下遍历同理。

• 时间复杂度$O(nm)$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @LastEditTime: 2026-03-25 22:05:04
 */
#define CHECK_AND_BREAK(now, sum) \
    if ((now) == (sum)) {         \
        return true;              \
    }                             \
    if ((now) > (sum)) {          \
        break;                    \
    }
typedef long long ll;
class Solution {
public:
    bool canPartitionGrid(vector<vector<int>>& grid) {
        ll sum = 0;
        for (vector<int>& row : grid) {
            for (int& v : row) {
                sum += v;
            }
        }
        if (sum % 2) {
            return false;
        }
        sum /= 2;

        ll now = 0;
        for (vector<int>& row : grid) {
            for (int& v : row) {
                now += v;
            }
            CHECK_AND_BREAK(now, sum)
        }

        now = 0;
        for (int j = 0; j < grid[0].size(); j++) {
            for (int i = 0; i < grid.size(); i++) {
                now += grid[i][j];
            }
            CHECK_AND_BREAK(now, sum)
        }

        return false;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源