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

【算法-哈希表3】四数相加2 和 赎金信

今天,带来哈希表相关算法的讲解。文中不足错漏之处望请斧正!

理论基础点这里


1. 四数相加2

分析题意

求符合条件的四元组的出现次数,条件:

  • nums1
  • nums2
  • nums3
  • nums4
    从四个数组中的每一个数组取一个数 num1, num2, num3, num4,满足 num1 + num2 + num3 + num4 == 0,则这是一个满足条件的四元组,可以记上它的出现次数。

题意转化

可以简单转化为 直接遍历取得4个数, 判断是否满足条件.但太慢,时间复杂度O(n^4)。

其实可以动动脑筋,将题意转化为 是否存在 两个两数之和 sum1 和 sum2 相加为0。

解决思路

四个数组该怎样去遍历,建立映射?

我们可以先遍历前两个数组,将数组中的元素两两求和得到sum1,把sum1和其出现次数建立映射得到哈希表sums1。接着遍历后两个数组,也两两求和得到sum2,在sums1中O(1)查找是否有一个和,和当前sum相加为0。

但为什么要这样遍历,我先遍历一个建立映射,再遍历三个不行吗?

这样我们在最终搜索比对的时候需要3层for来玩儿,那就是O(n^3)。而我们两两遍历只需要O(2 * n^2),这才是更好的。

编程实现

class Solution {
public:// 四数之和的判断 拆分为 两数之和的判断// 先遍历两个数组并求得所有两数之和sums1, 再遍历两个数组求剩下的两数之和, 查找是否有sum1 = -sum2int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int, int> sums1; // <sum1, cnt> -- 题目不要求返回下标, 只用返回次数int sum1 = 0;int sum2 = 0;// 先遍历两个数组并求得所有两数之和sums1for (int &num1 : nums1) {for (int &num2 : nums2) {sum1 = num1 + num2;++sums1[sum1];}}// 再遍历两个数组求剩下的两数之和, 查找是否有sum1 = -sum2int cnt = 0;for (int &num3 : nums3) {for (int &num4 : nums4) {sum2 = num3 + num4;auto iter = sums1.find(-sum2);if (iter != sums1.end()) cnt += iter->second;}}return cnt;}
};

时间复杂度:O(n^2)

2. 赎金信

分析题意

“给你两个字符串:ransomNote 和 magazine ,判断 ransomNote 能不能由 magazine 里面的字符构成。”

题意转化

判断ransomNote的组成字符是否全部都在magazine中有足够的字符与之对应。

解决思路

查找,上哈希。遍历magazine,用哈希表描述magazine中的字符出现过多少次。

编程实现

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {int appeared[26] = {0};// 用哈希表(数组)描述magazine中的哪些字符出现过.for (char &ch : magazine) ++appeared[ch - 'a'];// 在magazine中查找ransomNote的所有字符, 所有都能找到才是赎金信.for (char &ch : ransomNote) {--appeared[ch - 'a'];if (appeared[ch - 'a'] < 0) return false; // magazine中没有足够字符构成ransomNote}return true;}
};

时间复杂度:O(n)

空间复杂度:O(1)


今天的分享就到这里了,感谢您能看到这里。

这里是培根的blog,期待与你共同进步!

相关文章:

【算法-哈希表3】四数相加2 和 赎金信

今天&#xff0c;带来哈希表相关算法的讲解。文中不足错漏之处望请斧正&#xff01; 理论基础点这里 1. 四数相加2 分析题意 求符合条件的四元组的出现次数&#xff0c;条件&#xff1a; nums1nums2nums3nums4 从四个数组中的每一个数组取一个数 num1, num2, num3, num4&am…...

wpf devexpress自定义编辑器

打开前一个例子 步骤1-自定义FirstName和LastName编辑器字段 如果运行程序&#xff0c;会通知编辑器是空。对于例子&#xff0c;这两个未命名编辑器在第一个LayoutItem(Name)。和最终用户有一个访客左右编辑器查阅到First Name和Last Name字段&#xff0c;分别。如果你看到Go…...

文档向量化工具(一):Apache Tika介绍

Apache Tika是什么&#xff1f;能干什么&#xff1f; Apache Tika是一个内容分析工具包。 该工具包可以从一千多种不同的文件类型&#xff08;如PPT、XLS和PDF&#xff09;中检测并提取元数据和文本。 所有这些文件类型都可以通过同一个接口进行解析&#xff0c;这使得Tika在…...

学习c#的第二十一天

目录 C# 泛型&#xff08;Generic&#xff09; 泛型类型参数 类型参数的约束 约束多个参数 未绑定的类型参数 类型参数作为约束 notnull 约束 class 约束 default 约束 非托管约束 委托约束 枚举约束 类型参数实现声明的接口 泛型类 泛型方法 泛型和数组 泛型…...

Michael Jordan最新报告:去中心化机器学习中的契约、不确定性和激励

‍ ‍导读 11月3日&#xff0c;智源研究院学术顾问委员会委员、机器学习泰斗Michael Jordan在以“新一代人工智能前沿”为主题的2023北京论坛 新工科专题论坛上&#xff0c;发表了题为Contracts, Uncertainty, and Incentives in Decentralized Machine Learning&#xff08;去…...

3ds Max渲染用专业显卡还是游戏显卡?

使用3dsmax建模时&#xff0c;会面临诸多选择&#xff0c;除了用vr还是cr的决策&#xff0c;硬件选择上也存在着疑问&#xff0c;比如用专业显卡还是消费级游戏显卡&#xff1f;一般来说&#xff0c;除非是特别专业的大型项目和软件&#xff0c;且预算在5位数以上&#xff0c;常…...

airlearning-ue4安装的踩坑记录

最近要安装airlearning-ue4&#xff0c;用于实现无人机仿真环境&#xff0c;该项目地址为&#xff1a;GitHub - harvard-edge/airlearning-ue4: Environment Generator for Air Learning Project. This version is build on top of UE4 game engine 由于这个项目已经完成好几年…...

uniapp优化h5项目-摇树优化,gzip压缩和删除console.log

1.摇树优化 勾选摇树优化,打包删除死代码 2.gzip压缩和删除console.log 安装插件webpack和compression-webpack-plugin webpack插件 npm install webpack4.46.0 --save-devcompression-webpack-plugin插件 npm install compression-webpack-plugin6.1.1 --save-devconst Com…...

Pycharm之配置python虚拟环境

最近给身边的人写了脚本&#xff0c;在自己电脑可以正常运行。分享给我身边的人&#xff0c;却运行不起来&#xff0c;然后把报错的截图给我看了&#xff0c;所以难道不会利用pycharm搭建虚拟的环境&#xff1f;记录一下配置的过程。 第一步&#xff1a;右键要打开的python的代…...

如何使用MybatisPlus进行数据分页显示

如何使用MybatisPlus进行数据的分页呢&#xff1f; 使用Mybatis Plus提供的分页插件来简化开发&#xff0c;在MybatisPlusInterceptor的拦截器中添加自动分页的PaginationInnerInterceptor拦截器&#xff0c;当前配置需要交给spring的bean管理&#xff0c;类上添加注解Configu…...

代码随想录 Day49 单调栈01 LeetCode LeetCodeT739每日温度 T496 下一个最大元素I

前言 折磨的死去活来的动态规划终于结束啦,今天秋秋给大家带来两题非常经典的单调栈问题,可能你不清楚单调栈是什么,可以用来解决什么问题,今天我们就来一步一步的逐渐了解单调栈,到能够灵活使用单调栈.注意以下讲解中&#xff0c;顺序的描述为 从栈头到栈底的顺序 什么时候用单…...

高可用--限流熔断降级

熔断 熔断是应对微服务雪崩效应的一种链路保护机制。 场景 服务端出现问题 服务指标&#xff1a;响应时间、错误率、连续错误数等&#xff0c;超过阈值出发熔断。硬件指标&#xff1a;CPU、网络IO、内存 目的 服务端恢复需要时间、服务端需要休息避免全调用链路崩溃&…...

win10电脑无法联网,设置IPv4,点击属性无法打开,闪退

win10设置IPv4&#xff0c;点击属性无法打开&#xff0c;闪退 问题:win10设置IPv4&#xff0c;点击属性无法打开&#xff0c;闪退 问题:win10设置IPv4&#xff0c;点击属性无法打开&#xff0c;闪退 第1步&#xff1a;用管理员打开cmd命令窗口&#xff0c;然后输入下面的命令&…...

【数据结构】邻接表与邻接矩阵的转换

一.基本思想 1.邻接矩阵转换为邻接表&#xff1a; 先设置一个空的邻接表&#xff0c;然后查找邻接矩阵的值不为零元素&#xff0c;找到后在邻接表的单链表对应位置加入表边节点。 2.邻接表转换为邻接矩阵&#xff1a; 在邻接表上顺序取出每个表边结点&#xff0c;将邻接矩阵…...

VR智慧景区:VR赋能文旅产业,激活消费潜能

随着国家数字化战略的不断深入实施&#xff0c;文旅产业数字化转型的步伐也在逐渐加快&#xff0c;以VR技术赋能文旅产业&#xff0c;让文旅景区线上线下双渠道融合&#xff0c;进一步呈现文化底蕴、激活消费潜能。 VR智慧景区以沉浸式、互动式、科技感的方式&#xff0c;将景区…...

Spring Boot EasyPOI 使用指定模板导出Excel

相信大家都遇到过&#xff0c;用户提出要把界面上的数据导成一个Excel&#xff0c;还得是用户指定的Excel格式&#xff0c;用原生的POI&#xff0c;需要自己去实现&#xff0c;相信是比较麻烦的&#xff0c;所以我们可以使用开源的EasyPOI. 先上个图&#xff0c;看看是不是大家…...

postgresql:记录表膨胀引起的io问题的处理

文章目录 1. io异常2.查看profile报告2.1 生成事发时间段的pgprofile2.2 查看报告 3.检查table是否膨胀4.执行vacuum full5.总结 1. io异常 iostat -x 1 20 Device r/s w/s rkB/s wkB/s rrqm/s wrqm/s %rrqm %wrqm r_await w_await aqu-sz rareq…...

Windows下安装RabbitMQ

1.安装Erlang 因为RabbitMQ是用Erlang语言编写的&#xff0c;所以在安装RabbitMQ之前需要先安装Erlang。 如果还未安装Erlang&#xff0c;官方下载安装包&#xff0c;点击Download Windows installer下载Erlang Downloads - Erlang/OTP 下载Erlang/OTP后&#xff0c;双击otp的…...

广州华锐互动VRAR:利用VR开展刑事案件公安取证培训,沉浸式体验提升实战能力

随着科技的飞速发展&#xff0c;虚拟现实(VR)技术为我们的生活和工作带来了前所未有的便利。近年来&#xff0c;VR技术在刑事案件公安取证培训中的应用逐渐显现出其独特优势。通过模拟真实的犯罪现场&#xff0c;VR技术为学员提供了沉浸式的体验&#xff0c;使他们在安全的环境…...

消息消费过程

前言 本文介绍下Kafka消费过程, 内容涉及消费与消费组, 主题与分区, 位移提交&#xff0c;分区再平衡和消费者拦截器等内容。 消费者与消费组 Kafka将消费者组织为消费组, 消息只会被投递给消费组中的1个消费者。因此, 从不同消费组中的消费者来看, Kafka是多播(Pub/Sub)模式…...

Realistic Vision V5.1虚拟摄影棚效果验证:专业摄影师盲测准确率87.3%

Realistic Vision V5.1虚拟摄影棚效果验证&#xff1a;专业摄影师盲测准确率87.3% 1. 项目概述 Realistic Vision V5.1虚拟摄影棚是基于当前最先进的写实风格生成模型开发的本地化摄影工具。经过深度优化后&#xff0c;该工具能够生成与专业单反相机拍摄效果相媲美的人像作品…...

[认知计算] 神经网络架构:从生物启发的神经元到现代激活函数演进

1. 从生物神经元到人工神经元的数学抽象 1943年&#xff0c;麦卡洛克和皮茨在论文《神经活动中内在思想的逻辑演算》中首次提出用数学模型模拟生物神经元。这个看似简单的想法&#xff0c;彻底改变了人类对智能的认知方式。生物神经元由树突、细胞体和轴突三部分组成&#xff1…...

RWKV7-1.5B-g1a保姆级部署教程:离线加载+免外网依赖,中小企业AI落地首选

RWKV7-1.5B-g1a保姆级部署教程&#xff1a;离线加载免外网依赖&#xff0c;中小企业AI落地首选 1. 模型简介 rwkv7-1.5B-g1a 是基于新一代 RWKV-7 架构的多语言文本生成模型&#xff0c;专为中小企业AI落地场景优化设计。这个1.5B参数的轻量级模型在保持高质量生成能力的同时…...

Project Sistine核心代码剖析:从图像分割到鼠标事件模拟

Project Sistine核心代码剖析&#xff1a;从图像分割到鼠标事件模拟 【免费下载链接】sistine Turn a MacBook into a Touchscreen with $1 of Hardware 项目地址: https://gitcode.com/gh_mirrors/si/sistine Project Sistine是一个创新的开源项目&#xff0c;它能让普…...

如何用torchtext快速构建文本分类模型?5分钟上手RoBERTa与T5实战教程

如何用torchtext快速构建文本分类模型&#xff1f;5分钟上手RoBERTa与T5实战教程 【免费下载链接】text Models, data loaders and abstractions for language processing, powered by PyTorch 项目地址: https://gitcode.com/gh_mirrors/te/text 想要在PyTorch生态中快…...

vLLM-v0.17.1实战案例:为AI编程助手提供毫秒级代码补全服务

vLLM-v0.17.1实战案例&#xff1a;为AI编程助手提供毫秒级代码补全服务 1. vLLM框架简介 vLLM是一个专为大型语言模型(LLM)设计的高性能推理和服务库&#xff0c;其核心目标是提供极致的推理速度和易用性。这个项目最初由加州大学伯克利分校的天空计算实验室开发&#xff0c;…...

OpenClaw自动化周报:Qwen3-32B镜像整合多平台数据

OpenClaw自动化周报&#xff1a;Qwen3-32B镜像整合多平台数据 1. 为什么需要自动化周报 每周五下午&#xff0c;我的日历总会准时弹出提醒&#xff1a;"撰写本周工作总结"。这个看似简单的任务&#xff0c;实际操作起来却异常繁琐&#xff1a;需要登录JIRA查看任务…...

科研助手实战:OpenClaw驱动Qwen3.5-4B-Claude整理文献

科研助手实战&#xff1a;OpenClaw驱动Qwen3.5-4B-Claude整理文献 1. 为什么需要AI文献助手&#xff1f; 作为每周需要阅读数十篇论文的科研狗&#xff0c;我长期被三个问题困扰&#xff1a;一是PDF文献堆积如山却找不到关键结论&#xff1b;二是不同研究间的对比分析需要手动…...

CDN图片服务与动态参数优化

前言在现代Web应用中&#xff0c;图片已经不再是简单的静态资源&#xff0c;而是需要根据设备、网络、浏览器能力动态优化的核心内容。CDN图片服务提供了强大的动态处理能力&#xff0c;结合前端的智能参数拼接&#xff0c;可以实现图片加载的极致优化。一个典型的电商场景&…...

计算机毕业设计springboot基于的游戏后台管理系统 基于SpringBoot的网游运营管理平台的设计与实现 基于SpringBoot架构的电子竞技服务支撑系统的设计与实现

计算机毕业设计springboot基于的游戏后台管理系统&#xff08;配套有源码 程序 mysql数据库 论文&#xff09; 本套源码可以在文本联xi,先看具体系统功能演示视频领取&#xff0c;可分享源码参考。随着互联网技术的飞速发展和智能终端设备的全面普及&#xff0c;游戏产业已迅速…...