Medium

题目描述

给你一个 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

提示：

  • 有两种切割类型：水平切割或垂直切割。
  • 对于在第 r 行的水平切割 (0 <= r < m - 1)，将 grid 分为第0行…第r行 与 第r+1行…第m-1行，比较它们的和。
  • 对于在第 c 列的垂直切割 (0 <= c < n - 1)，将 grid 分为第0列…第c列 与 第c+1列…第n-1列，比较它们的和。
  • 暴力枚举所有可能的 r 和 c 切割；如果任何切割产生相等的部分和，返回 true。

解题思路

解题思路

这道题要求我们判断是否能通过一次水平或垂直切割将矩阵分成两个和相等的部分。

核心思路是使用前缀和优化：

  1. 预处理前缀和：计算每行的前缀和数组，这样可以快速计算任意列区间的和
  2. 水平切割枚举：尝试在每个可能的行位置进行水平切割，比较上下两部分的总和
  3. 垂直切割枚举：尝试在每个可能的列位置进行垂直切割，比较左右两部分的总和

对于垂直切割，我们需要计算左边所有列的总和与右边所有列的总和。利用行前缀和，可以在O(m)时间内计算出某个列区间在所有行中的元素总和。

算法步骤：

  1. 构建每行的前缀和数组
  2. 枚举所有可能的水平切割位置（在第i行和第i+1行之间）
  3. 枚举所有可能的垂直切割位置（在第j列和第j+1列之间）
  4. 对于每个切割位置，快速计算两部分的和并比较

时间复杂度主要来自于切割位置的枚举，通过前缀和预处理可以将每次和的计算优化到O(m)或O(1)。

代码实现

class Solution {
public:
    bool canPartitionGrid(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        // 计算每行的前缀和
        vector<vector<long long>> prefixSum(m, vector<long long>(n + 1, 0));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefixSum[i][j + 1] = prefixSum[i][j] + grid[i][j];
            }
        }
        
        // 尝试水平切割
        for (int r = 0; r < m - 1; r++) {
            long long topSum = 0, bottomSum = 0;
            for (int i = 0; i <= r; i++) {
                topSum += prefixSum[i][n];
            }
            for (int i = r + 1; i < m; i++) {
                bottomSum += prefixSum[i][n];
            }
            if (topSum == bottomSum) return true;
        }
        
        // 尝试垂直切割
        for (int c = 0; c < n - 1; c++) {
            long long leftSum = 0, rightSum = 0;
            for (int i = 0; i < m; i++) {
                leftSum += prefixSum[i][c + 1];
                rightSum += prefixSum[i][n] - prefixSum[i][c + 1];
            }
            if (leftSum == rightSum) return true;
        }
        
        return false;
    }
};

class Solution:
    def canPartitionGrid(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        
        # 计算每行的前缀和
        prefix_sum = []
        for i in range(m):
            row_prefix = [0]
            for j in range(n):
                row_prefix.append(row_prefix[-1] + grid[i][j])
            prefix_sum.append(row_prefix)
        
        # 尝试水平切割
        for r in range(m - 1):
            top_sum = sum(prefix_sum[i][n] for i in range(r + 1))
            bottom_sum = sum(prefix_sum[i][n] for i in range(r + 1, m))
            if top_sum == bottom_sum:
                return True
        
        # 尝试垂直切割
        for c in range(n - 1):
            left_sum = sum(prefix_sum[i][c + 1] for i in range(m))
            right_sum = sum(prefix_sum[i][n] - prefix_sum[i][c + 1] for i in range(m))
            if left_sum == right_sum:
                return True
        
        return False

public class Solution {
    public bool CanPartitionGrid(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        
        // 计算每行的前缀和
        long[,] prefixSum = new long[m, n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                prefixSum[i, j + 1] = prefixSum[i, j] + grid[i][j];
            }
        }
        
        // 尝试水平切割
        for (int r = 0; r < m - 1; r++) {
            long topSum = 0, bottomSum = 0;
            for (int i = 0; i <= r; i++) {
                topSum += prefixSum[i, n];
            }
            for (int i = r + 1; i < m; i++) {
                bottomSum += prefixSum[i, n];
            }
            if (topSum == bottomSum) return true;
        }
        
        // 尝试垂直切割
        for (int c = 0; c < n - 1; c++) {
            long leftSum = 0, rightSum = 0;
            for (int i = 0; i < m; i++) {
                leftSum += prefixSum[i, c + 1];
                rightSum += prefixSum[i, n] - prefixSum[i, c + 1];
            }
            if (leftSum == rightSum) return true;
        }
        
        return false;
    }
}

var canPartitionGrid = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    
    // Calculate total sum
    let totalSum = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            totalSum += grid[i][j];
        }
    }
    
    // If total sum is odd, can't partition into equal halves
    if (totalSum % 2 !== 0) return false;
    
    const target = totalSum / 2;
    
    // Try horizontal cuts (between rows)
    let currentSum = 0;
    for (let i = 0; i < m - 1; i++) {
        for (let j = 0; j < n; j++) {
            currentSum += grid[i][j];
        }
        if (currentSum === target) return true;
    }
    
    // Try vertical cuts (between columns)
    currentSum = 0;
    for (let j = 0; j < n - 1; j++) {
        for (let i = 0; i < m; i++) {
            currentSum += grid[i][j];
        }
        if (currentSum === target) return true;
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m×n) - 预处理前缀和需要O(m×n)，枚举水平切割位置需要O(m²)，枚举垂直切割位置需要O(n×m)，总体为O(m×n + m² + n×m) = O(m×n)
空间复杂度O(m×n) - 需要存储每行的前缀和数组