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)


相关推荐

  • equals和==的区别

    equals和==的区别

  • java培训机构_南阳清大教育培训机构

    java培训机构_南阳清大教育培训机构正文谈到MYSQL的事物,相信大家对这几个概念都不会陌生:四大特性:ACID并发问题脏读不可重复读幻读隔离级别ReadUncommitted(读未提交)ReadCommitted(读提交)RepeatableRead(可重读)Serializable(可串行化)下面的思维导图可能更表达得清晰????MySQL的默认事物隔离级别是RR(RepeatableRead),可重复读级别是能够解决脏读、不可重复读的这两个事物并发问题的,但是幻读的问题仍

  • 查看Python安装路径_Python安装路径

    查看Python安装路径_Python安装路径查看Python安装路径方法在使用python的时候,有时候会需要找到python包的安装位置,怎么办?法一、对于Windows平台,打开cmd输入命令wherePython,回车(即按下Enter键)可输出Python的安装路径。参见下图:【如何清除命令行窗口内容输入cls回车】法二、在IDLE(Python自带的简洁的集成开发环境)中先输入impor…

  • PKCS11接口解析「建议收藏」

    PKCS11接口解析「建议收藏」pkcs密码中间件位于上层应用和底层安全设备之间,应用基于PKCS#11标准接口开发各类应用程序。主要包括2个库主API库:提供给应用的PKCS11接口。 tokenDLL库:由主API库调用,完成从上向下到指定设备的套接。 安全密码设备:安全服务资源和实施的载体,完成具体安全功能支撑。表pkcs11函数接口 种类 函数 …

  • vsftp怎么用_不使用网络客户端怎么设置

    vsftp怎么用_不使用网络客户端怎么设置FTPDocument1FTP支持两种模式。这两种模式被称为“标准”(或“主动”)模式和“被动”(或“PASV”)模式。“标准”模式FTP客户端向FTP服务器发送PORT命令。“被动”模式客户端向FTP服务器发送PASV命令。这两条命令是通过FTP命令通道发送的。“标准”模式FTP客户端首先建立一个到FTP服务器上TCP端口21的连接。此连接会建立FTP命令通道。当FTP客户端需要接收数据(例如文…

  • 流氓软件原理及防范

    流氓软件原理及防范本人不擅长表述,本章以问答形式进行1.我该怎么去寻找需要的软件?百度,Google,官网,以及一些熟知的网站,例如:脚本之家,吾爱激活成功教程,csdn,游侠,东坡下载等等,虽然有些网站一股浓浓的山寨感,但是却包含了大量的资源,比起不知名的网站,已经属于比较好的,并且部分网站社区的风格是由于建站时间较长,以前遗留的产物2.我需要注意什么?百度前两条很有可能是广告,并且由于百度竞价的存在,排在前面的不一定是想要的或最好的,没事多看几页注意文件大小,这里大小是真实下载时浏览器反馈的文件大小,是否符合常理

发表回复

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

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