leetcode-1074. 元素和为目标值的子矩阵数量(前缀和+hash)

leetcode-1074. 元素和为目标值的子矩阵数量(前缀和+hash)给出矩阵 matrix 和目标值 target,返回元素总和等于目标值的非空子矩阵的数量。子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。如果 (x1, y1, x2, y2) 和 (x1’, y1’, x2’, y2’) 两个子矩阵中部分坐标不同(如:x1 != x1’),那么这两个子矩阵也不同。示例 1:输入:matrix = [[0,1,0],[1,1,1],

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

给出矩阵 matrix 和目标值 target,返回元素总和等于目标值的非空子矩阵的数量。

子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。

如果 (x1, y1, x2, y2) 和 (x1’, y1’, x2’, y2’) 两个子矩阵中部分坐标不同(如:x1 != x1’),那么这两个子矩阵也不同。
在这里插入图片描述

示例 1:



输入:matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
输出:4
解释:四个只含 0 的 1x1 子矩阵。
示例 2:

输入:matrix = [[1,-1],[-1,1]], target = 0
输出:5
解释:两个 1x2 子矩阵,加上两个 2x1 子矩阵,再加上一个 2x2 子矩阵。
示例 3:

输入:matrix = [[904]], target = 0
输出:0
 

提示:

1 <= matrix.length <= 100
1 <= matrix[0].length <= 100
-1000 <= matrix[i] <= 1000
-10^8 <= target <= 10^8
class Solution { 

public:
void re(vector<int> &a){ 

for(auto &w : a)w = 0;
}
int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) { 

int n = matrix.size(),m = matrix[0].size();
vector<int>cols(m,0);
unordered_map<int,int>mm;
int ans = 0;
vector<int>s(m + 1,0);
for(int i = 0;i < n;i ++){ 

re(cols);
re(s);
for(int j = i;j < n;j ++){ 

mm.clear();
mm[0] = 1;
for(int k = 1;k <= m;k ++){ 

cols[k - 1] += matrix[j][k - 1];
s[k] = s[k - 1] + cols[k - 1];
}
for(int k = 1;k <= m;k ++){ 

ans += mm[s[k] - target];
if(!mm.count(s[k]))mm[s[k]] = 0;
mm[s[k]] ++;
}
}
}
return ans;
}
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/169063.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • ECLIPSE软件安装MyBatis插件 MyBatis Generator

    ECLIPSE软件安装MyBatis插件 MyBatis GeneratorECLIPSE软件安装MyBatis插件打开Eclipse->导航栏Help->EclipseMarketplace会出现如下页面:搜索mybatis->安装我红框框的东西安装就是同意安装,然后install之类的…安装好之后会提示重启Eclipse…

  • 正则表达式替换部分内容

    正则表达式替换部分内容总结一个正则表达式替换匹配项部分内容的语法(.)小括号中的内容是可以用$num进行引用比如123ready,用[0-9]{3}(.)匹配,然后$1可以引用(.*)中的内容,此处(.)代表其他符号如图可以匹配3个数字接其他字符的模式替换结果后续需要将正则语法做一个简要汇总方便温习(…

  • java反射的实现_c程序设计

    java反射的实现_c程序设计Java程序设计(高级及专题)- 类的加载和反射

  • tcp攻击脚本_防御的意思

    tcp攻击脚本_防御的意思目录相关原理(tcp基础)实例演示关于防御措施相关原理(tcp基础)三次握手:TCP是基于IP网络层之上的传输层协议,用于端到端的可靠的字节流传输。过程:1.C向S发送连接请求,标记位SYN设为1,且随机设置序列号seq2.S返回确认消息,ACK设为seq+1,标记位SYN设为1,随机序列号seq3.C返回确认消息,ACK设为seq+1四次挥手:四次挥手指正常连接中断的情况。过程:…

  • ribbon的负载均衡策略_f5负载均衡配置

    ribbon的负载均衡策略_f5负载均衡配置在这里吐槽一句:网上很多文章真是神坑,你不看还好,看了只会问题越来越多,就连之前的问题都没有解决!!!不多说了,Ribbon作为后端负载均衡器,比Nginx更注重的是请求分发而不是承担并发,可以直接感知后台动态变化来指定分发策略。它一共提供了7种负载均衡策略:策略名策略声明策略描述实现说明

    2022年10月13日
  • 本以为java语言很难学,其实就学完下面这些知识,就能理解了

    本以为java语言很难学,其实就学完下面这些知识,就能理解了刚毕业,找工作,很多人都面临相同的问题。自己能做什么?什么工作既舒服,福利又好(不存在的,除非银行你家开的)。然后社会是个发展的社会,现代人的生活越来越智能,生活中其实充满“技术”!!!所以,在各个岗位中,其实编程类的岗位工资是平均水平最高的。可以加你Java资料分享群java《学习》+交流523401738作为5大编程语言的JAVA是当今最受各大公司的青睐,很多项目,很多工程都需要用到java…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号