当前位置: 首页 > news >正文

LeetCode 1074:元素和为目标值的子矩阵数量

LeetCode 1074:元素和为目标值的子矩阵数量

在这里插入图片描述

问题定义与核心挑战

给定二维矩阵 matrix 和目标值 target,需统计 所有和为 target 的非空子矩阵数量。直接枚举所有子矩阵的时间复杂度为 O(m²n²)mn 为矩阵行列数),无法通过大数据用例,因此需要降维优化

核心思路:二维转一维 + 前缀和哈希表

将二维问题转化为多个一维子问题

  1. 固定上下边界:遍历所有可能的上边界 top 和下边界 bottom,将两边界之间的列和压缩为一维数组 colSumcolSum[col] 表示 topbottom 行、第 col 列的和)。
  2. 一维子数组统计:对 colSum 数组,使用前缀和 + 哈希表的方法,统计和为 target 的子数组数量(时间复杂度 O(n))。

算法步骤详解

步骤 1:遍历上下边界
  • 枚举所有可能的上边界 top(从第 0 行到第 m-1 行)。
  • 对每个 top,初始化 colSum 数组(记录列和),并枚举下边界 bottom(从 top 到第 m-1 行)。
步骤 2:更新列和数组 colSum

对于当前 bottom,将 matrix[bottom][col] 累加到 colSum[col] 中,得到 topbottom 行的列和。

步骤 3:统计一维子数组和为 target 的数量

colSum 数组,使用前缀和 + 哈希表

  • 前缀和 currentSum:记录当前遍历到第 col 列时的前缀和(前 col+1 列的和)。
  • 哈希表 prefixCounts:记录前缀和出现的次数(初始时 prefixCounts.put(0, 1),表示前缀和为 0 的情况,对应子数组从第 0 列开始)。
  • 对于每个列和 num
    • 计算 need = currentSum - target,若 need 存在于 prefixCounts,则累加对应次数(即存在以当前列为结尾的子数组和为 target)。
    • 更新 currentSum 并记录到 prefixCounts 中。

完整代码(Java)

import java.util.HashMap;
import java.util.Map;class Solution {public int numSubmatrixSumTarget(int[][] matrix, int target) {int m = matrix.length;int n = matrix[0].length;int ans = 0;// 枚举上边界 topfor (int top = 0; top < m; top++) {int[] colSum = new int[n]; // 记录当前上下边界之间的列和// 枚举下边界 bottom(从 top 开始,逐步扩展)for (int bottom = top; bottom < m; bottom++) {// 更新列和:加上当前行 bottom 的元素for (int col = 0; col < n; col++) {colSum[col] += matrix[bottom][col];}// 统计当前 colSum 中,和为 target 的子数组数量ans += countSubarrays(colSum, target);}}return ans;}/*** 统计一维数组 nums 中,和为 target 的子数组数量* 使用前缀和 + 哈希表优化,时间复杂度 O(n)*/private int countSubarrays(int[] nums, int target) {int count = 0;int currentSum = 0;Map<Integer, Integer> prefixCounts = new HashMap<>();prefixCounts.put(0, 1); // 初始状态:前缀和为 0 出现 1 次(对应空数组)for (int num : nums) {currentSum += num;// 寻找是否存在前缀和为 currentSum - target 的情况int need = currentSum - target;if (prefixCounts.containsKey(need)) {count += prefixCounts.get(need);}// 更新当前前缀和的出现次数prefixCounts.put(currentSum, prefixCounts.getOrDefault(currentSum, 0) + 1);}return count;}
}

复杂度分析

  • 时间复杂度O(m²n)

    • 外层遍历上下边界:O(m²)m 行,每行最多遍历 m 次)。
    • 内层处理列和与一维子数组:O(n)(每轮列和更新 O(n),一维统计 O(n))。
      总复杂度为 O(m² × n),对于 m=100n=100,计算量为 100²×100=1e6,高效可行。
  • 空间复杂度O(n)

    • colSum 数组和哈希表最多占用 O(n) 空间(n 为列数)。

示例验证

示例 1(输入 matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0):
  • top=0bottom=0 时,colSum = [0,1,0],统计得 2 个 子数组([0][0])。
  • top=2bottom=2 时,colSum = [0,1,0],同样统计得 2 个 子数组。
  • 总数量为 2+2=4,符合示例输出。
示例 2(输入 matrix = [[1,-1],[-1,1]], target = 0):
  • top=0bottom=1 时,colSum = [0,0],统计得 3 个 子数组([0][0,0][0])。
  • 结合其他边界组合,最终总数量为 5,符合示例输出。

该方法通过二维转一维前缀和哈希表,高效将复杂度从 O(m²n²) 降至 O(m²n),是处理二维子矩阵和问题的经典优化思路。

http://www.lryc.cn/news/600290.html

相关文章:

  • OGG同步Oracle到Kafka不停库,全量加增量
  • 【愚公系列】《MIoT.VC》003-构建基本仿真工作站(组件的属性、行为、视频展示)
  • Javaweb————什么是超文本传输协议?
  • HiggsAudio-V2: 融合语言与声音的下一代音频大模型
  • 详解力扣高频SQL50题之550. 游戏玩法分析 IV【中等】
  • 原理篇..
  • 2025年入局苹果Vision Pro开发:从零到发布的完整路线图
  • 路由选择工具——IP-Prefix
  • Triton Server部署Embedding模型
  • 谷粒商城170缓存序列化报错
  • 如何查看电脑后门IP和流量?
  • 图论:Dijkstra算法
  • CPU 为什么需要缓存?揭开速度与效率的底层逻辑
  • 大模型应用班-第2课 DeepSeek使用与提示词工程课程重点 学习ollama 安装 用deepseek-r1:1.5b 分析PDF 内容
  • 机器学习——随机森林算法分类问题案例解析(sklearn)
  • Linux系统架构核心全景详解
  • HAProxy 实验指南:从零开始搭建高可用负载均衡系统
  • sssss
  • mybatis-plus从入门到入土(三):持久层接口之IService
  • 嵌入式硬件篇---有线串口通信问题解决
  • 如何创建或查看具有 repo 权限的 GitHub 个人访问令牌(PAT)
  • 国内AI IDE竞逐:腾讯CodeBuddy、阿里通义灵码、字节跳动TRAE、百度文心快码
  • 零弹窗干扰的贪吃蛇游戏,下载即玩
  • 刷题日记0726
  • 二次函数图像动画展示
  • ESP32实战:5分钟实现PC远程控制LED灯
  • 【MySQL 数据库】MySQL基本查询(第二节)
  • AutoCAD_2025下载与保姆级安装教程
  • 联表实现回显功能
  • 速通python加密之AES加密