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

代码随想录算法训练营第七天| 哈希表理论基础 454.四数相加II 383.赎金信 15.三数之和 18.四数之和

454. 四数相加 II

题目

给定四个包含整数的数组 A, B, C, D,计算有多少个元组 (i, j, k, l) 使得 A[i] + B[j] + C[k] + D[l] = 0

解题思路

  • 先计算数组 AB 的所有组合和,并存入哈希表 map 中,键为组合和,值为该和出现的次数。
  • 然后遍历数组 CD 的所有组合,查找 -(C[k] + D[l]) 是否存在于 map 中,如果存在则累加结果。

反思

使用哈希表可以有效地降低时间复杂度,从 O(n^4) 降到 O(n^2),提高了效率。

代码

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res = 0;Map<Integer, Integer> map = new HashMap<>();for(int i : nums1) {for(int j : nums2) {int sum = i + j;map.put(sum, map.getOrDefault(sum, 0) + 1);}}for(int i : nums3) {for(int j : nums4) {res += map.getOrDefault(0 - i - j, 0);}}return res;}
}

383. 赎金信

题目

给定一个赎金信字符串和一个杂志字符串,判断赎金信能否由杂志中的字符构成。每个字符只能使用一次。

解题思路

  • 创建一个长度为 26 的数组,用于记录每个字母在杂志中出现的次数。
  • 遍历赎金信,检查数组中对应字母的计数,如果不足则返回 false,否则减一。

反思

直接使用数组存储字符频次比使用哈希表更简单,并且减少了空间占用。

代码

class Solution {public boolean canConstruct(String ransomNote, String magazine) {if(ransomNote.length() > magazine.length()) {return false;}int[] nums = new int[26];for(char i : magazine.toCharArray()) {nums[i - 'a'] += 1;}for(char i : ransomNote.toCharArray()) {if(nums[i - 'a'] == 0) {return false;} else {nums[i - 'a'] -= 1;}}return true;}
}

15. 三数之和

题目

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a, b, c 使得 a + b + c = 0,找出所有满足条件且不重复的三元组。

解题思路

  • 先对数组排序,然后使用双指针法。
  • 遍历每个元素 a,固定 a 后,使用左右指针寻找 bc 使得 a + b + c = 0
  • 为避免重复结果,需要跳过重复元素。

反思

使用 while 循环去重是必须的,尤其在左右指针移动时对比的数要注意防止重复。

代码

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums);for(int i = 0; i < nums.length; i++) {if (nums[i] > 0) {return result;}if (i > 0 && nums[i] == nums[i - 1]) {continue; // 去重 a}int left = i + 1, right = nums.length - 1;while (left < right) {int sum = nums[i] + nums[left] + nums[right];if (sum > 0) {right--;} else if (sum < 0) {left++;} else {result.add(Arrays.asList(nums[i], nums[left], nums[right]));while (left < right && nums[left] == nums[left + 1]) left++;while (left < right && nums[right] == nums[right - 1]) right--;left++;right--;}}}return result;}
}

18. 四数之和

题目

给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a, b, c, d 使得 a + b + c + d = target,找出所有满足条件且不重复的四元组。

解题思路

  • 对数组进行排序,然后使用两层循环固定前两个元素,再使用双指针寻找后两个元素。
  • 注意跳过重复元素,防止结果重复。

反思

if 语句用于去重时比 while 更合适,因为只需要一次性跳过重复的前一个元素。

代码

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(nums);for (int i = 0; i < nums.length - 3; i++) {if (nums[i] > target && nums[i] >= 0) {break;}if (i > 0 && nums[i] == nums[i - 1]) {continue;}for (int j = i + 1; j < nums.length - 2; j++) {if (nums[i] + nums[j] > target && nums[i] + nums[j] >= 0) {break;}if (j > i + 1 && nums[j] == nums[j - 1]) {continue;}int left = j + 1, right = nums.length - 1;while (left < right) {int sum = nums[i] + nums[j] + nums[left] + nums[right];if (sum > target) {right--;} else if (sum < target) {left++;} else {result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));while (left < right && nums[left] == nums[left + 1]) left++;while (left < right && nums[right] == nums[right - 1]) right--;left++;right--;}}}}return result;}
}

相关文章:

代码随想录算法训练营第七天| 哈希表理论基础 454.四数相加II 383.赎金信 15.三数之和 18.四数之和

454. 四数相加 II 题目 给定四个包含整数的数组 A, B, C, D&#xff0c;计算有多少个元组 (i, j, k, l) 使得 A[i] B[j] C[k] D[l] 0。 解题思路 先计算数组 A 和 B 的所有组合和&#xff0c;并存入哈希表 map 中&#xff0c;键为组合和&#xff0c;值为该和出现的次数…...

搜维尔科技:Manus新品发布Metagloves Pro专业版,专为高精度需求的客户打造,尤其是人形机器人产业与人机工效研究使用

manus新品发布Metagloves Pro专业版&#xff0c;专为高精度需求的客户打造&#xff0c;尤其是人形机器人产业与人机工效研究使用 搜维尔科技&#xff1a;manus新品发布Metagloves Pro专业版&#xff0c;专为高精度需求的客户打造&#xff0c;尤其是人形机器人产业与人机工效研究…...

Spring Boot实现的动态化酒店住宿管理系统

1系统概述 1.1 研究背景 随着计算机技术的发展以及计算机网络的逐渐普及&#xff0c;互联网成为人们查找信息的重要场所&#xff0c;二十一世纪是信息的时代&#xff0c;所以信息的管理显得特别重要。因此&#xff0c;使用计算机来管理酒店客房管理系统的相关信息成为必然。开发…...

数字IC后端实现Innovus |给各种IP子模块添加port buffer和antenna diode万能脚本

我们之前分享过在hierarchical flow后端实现中为了确保顶层flatten时timing signoff和physical signoff看到的情况和模块级看到的情况一致&#xff0c;我们会在模块io port添加io port buffer&#xff08;主要是timing&#xff0c;antenna一致性&#xff09;。实际上在芯片级我…...

反向代理服务器---NGINX

1.NGINX NGINX&#xff08;发音为“engine-x”&#xff09;是一个开源的高性能HTTP服务器和反向代理服务器。它被广泛用于互联网应用程序的加速、负载均衡和高可用性的配置。NGINX具有低内存消耗、高并发能力和卓越的性能&#xff0c;能够处理大量并发连接和高流量的网络流量。…...

unity3d————场景管理类SceneManager

常用API SceneManager.LoadScene(string sceneName) 加载名为 sceneName 的场景。SceneManager.LoadScene(int sceneBuildIndex) 根据场景在Build设置中的索引加载场景。SceneManager.GetActiveScene() 获取当前活动的场景。SceneManager.GetSceneByName(string name) 根据名称…...

鹅厂面试官:Transformer 为何需要位置编码?

最近这一两周看到不少互联网公司都已经开始秋招发放Offer。 不同以往的是&#xff0c;当前职场环境已不再是那个双向奔赴时代了。求职者在变多&#xff0c;HC 在变少&#xff0c;岗位要求还更高了。 最近&#xff0c;我们又陆续整理了很多大厂的面试题&#xff0c;帮助一些球…...

MySQL数据库学习指南

一、数据库的库操作 1、创建数据库 2、删除数据库 3、查看数据库 4、选择数据库 5、修改数据库 6、数据库备份与恢复 7、数据库的权限管理 二、数据库的表操作 1、创建表 2、删除表 3、修改表 4、查看表的结构 5、查看表的数据 6、创建索引 7、删除索引 8、约束…...

算法刷题-小猫爬山

本题来源165. 小猫爬山 - AcWing题库 翰翰和达达饲养了 NN 只小猫&#xff0c;这天&#xff0c;小猫们要去爬山。 经历了千辛万苦&#xff0c;小猫们终于爬上了山顶&#xff0c;但是疲倦的它们再也不想徒步走下山了&#xff08;呜咕>_<&#xff09;。 翰翰和达达只好花…...

Maven项目管理工具-初始+环境配置

1. Maven的概念 1.1. 什么是Maven Maven是跨平台的项目管理工具。主要服务于基于Java平台的项目构建&#xff0c;依赖管理和项目信息管理。 理想的项目构建&#xff1a;高度自动化&#xff0c;跨平台&#xff0c;可重用的组件&#xff0c;标准化的流程 maven能够自动下载依…...

【JavaEE初阶】网络编程TCP协议实现回显服务器以及如何处理多个客户端的响应

前言 &#x1f31f;&#x1f31f;本期讲解关于TCP/UDP协议的原理理解~~~ &#x1f308;感兴趣的小伙伴看一看小编主页&#xff1a;GGBondlctrl-CSDN博客 &#x1f525; 你的点赞就是小编不断更新的最大动力 &#x1f386;那么废话不多说…...

Android 中的串口开发

一&#xff1a;背景 本文着重讲安卓下的串口。 由于开源的Android在各种智能设备上的使用越来越多&#xff0c;如车载系统等。在我们的认识中&#xff0c;Android OS的物理接口一般只有usb host接口和耳机接口&#xff0c;但其实安卓支持各种各样的工业接口&#xff0c;如HDM…...

TensorRt OP

在TensorRT中&#xff0c;OP&#xff08;Operations&#xff0c;操作&#xff09;是指网络中的基本计算单元&#xff0c;类似于数学中的运算符。每个OP执行一个特定的计算任务&#xff0c;例如卷积、矩阵乘法、激活函数等。TensorRT通过识别和优化这些OP来提高深度学习模型的推…...

构建负责任的人工智能:数据伦理与隐私保护

构建负责任的人工智能&#xff1a;数据伦理与隐私保护 目录 &#x1f31f; 数据伦理的重要性&#x1f4ca; 公平性评估&#xff1a;实现无偏差的模型&#x1f512; 数据去标识化&#xff1a;保护用户隐私的必要手段&#x1f50d; 透明性与问责&#xff1a;建立可信的数据处理…...

微信小程序live-pusher和video同时使用,video播放声音时时大时小

一、遇到的问题 微信小程序live-pusher和video同时使用,video播放声音时有时无时大时小 二、排查流程 业务是模拟面试,每道题一个推流live-pusher和一个面试题video,一次面试有多道面试题,页面就一个live-pusher和一个video,切换面试题时给live-pusher和video重新赋值u…...

MySQL 分库分表实战

在当今互联网时代&#xff0c;数据量的增长呈爆炸式趋势&#xff0c;传统的单库单表架构已经难以满足大规模数据存储和高并发访问的需求。MySQL 分库分表技术应运而生&#xff0c;它可以有效地提高数据库的性能、扩展性和可用性。本文将详细介绍 MySQL 分库分表的实战经验。 一…...

MySQL—CRUD—进阶—(二) (ಥ_ಥ)

文本目录&#xff1a; ❄️一、新增&#xff1a; ❄️二、查询&#xff1a; 1、聚合查询&#xff1a; 1&#xff09;、聚合函数&#xff1a; 2&#xff09;、GROUP BY子句&#xff1a; 3&#xff09;、HAVING 子句&#xff1a; 2、联合查询&#xff1a; 1&#xff09;、内连接…...

时序分解 | TTNRBO-VMD改进牛顿-拉夫逊算法优化变分模态分解

时序分解 | TTNRBO-VMD改进牛顿-拉夫逊算法优化变分模态分解 目录 时序分解 | TTNRBO-VMD改进牛顿-拉夫逊算法优化变分模态分解效果一览基本介绍程序设计参考资料 效果一览 基本介绍 (创新独家)TTNRBO-VMD改进牛顿-拉夫逊优化算优化变分模态分解TTNRBO–VMD 优化VMD分解层数K和…...

2024“源鲁杯“高校网络安全技能大赛-Misc-WP

Round 1 hide_png 题目给了一张图片&#xff0c;flag就在图片上&#xff0c;不过不太明显&#xff0c;写个python脚本处理一下 from PIL import Image ​ # 打开图像并转换为RGB模式 img Image.open("./attachments.png").convert("RGB") ​ # 获取图像…...

CSS行块标签的显示方式

块级元素 标签&#xff1a;h1-h6&#xff0c;p,div,ul,ol,li,dd,dt 特点&#xff1a; &#xff08;1&#xff09;如果块级元素不设置默认宽度&#xff0c;那么该元素的宽度等于其父元素的宽度。 &#xff08;2&#xff09;所有的块级元素独占一行显示. &#xff08;3&#xff…...

Go 语言中的 for range 循环教程

在 Go 语言中&#xff0c;for range 循环是一个方便的语法结构&#xff0c;用于遍历数组、切片、映射和字符串。本教程将通过示例代码来帮助理解如何在 Go 中使用 for range 循环。 package mainimport "fmt"func main() {// 遍历切片并计算和nums : []int{2, 3, 4}…...

青训营 X 豆包MarsCode 技术训练营--小M的比赛胜场计算

问题描述 小M参加了一场n个人的比赛&#xff0c;比赛规则是所有选手两两对决。每个人有一个能力值&#xff0c;对应着他们的序号。参赛者同时被分为黄色或蓝色两种颜色。比赛胜负的规则如下&#xff1a; 当比赛双方颜色不同时&#xff0c;能力值大的选手获胜&#xff1b; 当比…...

海王3纯源码

海王3是一款热门的捕鱼类游戏&#xff0c;其纯源码为开发者提供了一个完整的游戏开发基础。该源码包括客户端和服务端的完整架构&#xff0c;支持多人在线竞技模式和丰富的游戏玩法。服务端采用C语言编写&#xff0c;并使用MySQL数据库来存储玩家数据&#xff0c;确保数据处理的…...

【ShuQiHere】Linux 系统中的硬盘管理详解:命令与技巧

【ShuQiHere】 &#x1f4bd; 在 Linux 系统中&#xff0c;硬盘管理不仅仅是存储数据的操作&#xff0c;更涉及系统性能、数据安全和稳定性的优化。无论你是系统管理员、开发者还是 Linux 爱好者&#xff0c;掌握硬盘管理的基础操作都非常有用。本文将从硬盘健康检查、分区管理…...

数据结构之堆和二叉树的简介

1.树 1.1 树的概念与结构 如图所示&#xff0c;树是⼀种非线性的数据结构&#xff0c;它是由 n &#xff08;n>0&#xff09; 个有限结点组成⼀个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树&#xff0c;也就是说它是根朝上&#xff0c;而叶朝下的。 …...

微信小程序上传图片添加水印

微信小程序使用wx.chooseMedia拍摄或从手机相册中选择图片并添加水印&#xff0c; 代码如下&#xff1a; // WXML代码&#xff1a;<canvas canvas-id"watermarkCanvas" style"width: {{canvasWidth}}px; height: {{canvasHeight}}px;"></canvas&…...

xshell5找不到匹配的host key算法

xshell5找不到匹配的host key算法&#xff0c;是因为电脑客户端不支持服务器的算法&#xff0c;因此需要再服务器增加算法。 下面以Ubuntu系统为例&#xff0c;修改下面的文件 sudo vim /etc/ssh/sshd_config 增加下面算法 KexAlgorithms diffie-hellman-group-exchange-…...

Linux中安装Tomcat

文章目录 一、Tomcat介绍1.1、Tomcat是什么1.2、Tomcat的工作原理1.3、Tomcat适用的场景1.4、Tomcat与Nginx、Apache比较1.4.1、优势1.4.2、劣势1.4.3、定位功能 1.5、Tomcat 的主要组件1.6、Tomcat 的主要配置文件 二、Tomcat安装2.1、查看可用的JDK2.2、安装OpenJDK 112.3、配…...

RV1126音视频学习(二)-----VI模块

文章目录 前言2.RV1126的视频输入vi模块2.1什么是VI模块2.3RV1126VI模块主要APIRK_MPI_SYS_Init()RK_MPI_VI_SetChnAttrRK_MPI_VI_EnableChnRK_S32 RK_MPI_VI_DisableChnRK_MPI_VI_StartStreamRK_MPI_SYS_GetMediaBufferRK_MPI_MB_GetPtrRK_MPI_MB_GetSizeRK_MPI_MB_ReleaseBuf…...

「C/C++」C++17 之 std::string_view 轻量级字符串视图

✨博客主页何曾参静谧的博客&#x1f4cc;文章专栏「C/C」C/C程序设计&#x1f4da;全部专栏「VS」Visual Studio「C/C」C/C程序设计「UG/NX」BlockUI集合「Win」Windows程序设计「DSA」数据结构与算法「UG/NX」NX二次开发「QT」QT5程序设计「File」数据文件格式「PK」Parasoli…...

陕西专业网站开发公司/昆明优化网站公司

最近项目中有个在EditText中输入子网掩码(xxx.xxx.xxx.xxx)形式的需求&#xff0c;只需 手动填入数字&#xff0c;自动添加”.”进去。于是想到了EditText的addTextChangedListener&#xff0c; 不过在editText.setText()时就碰到了问题&#xff0c;报了java.lang.StackOverf…...

中国建设银行网站打不开/网络营销的模式有哪些?

为什么我上传一张特定的图片一直是这个异常&#xff0c;但是图片能上传到服务器&#xff0c;save保存方法也没执行成功没插入到数据库中&#xff0c;是不是跟我那个保存方法里面其他东西有关&#xff0c;这个跟图片大小无关&#xff0c;因为上传比它大的图片保存方法都能成功ja…...

在别的公司做的网站可以转走吗/北京网络优化推广公司

一、viewport宽度 起源&#xff1a;PC端的网站要显示在移动端有什么问题&#xff1f; 如果把移动端的可是区域设置到&#xff08;320-768&#xff09;的话&#xff0c;大部分网站都会因为太窄而显示错乱所以浏览器默认把viewport【这个viewport指的是layout viewport】设置为一…...

镇江怎么样/seo核心技术排名

Spring Security 借助一系列Servlet Filter 来提供安全性功能&#xff0c;但是借助Spring的小技巧&#xff0c;我们只需要配置一个Filer就可以了&#xff0c;DelegatingFilterProxy是一个特殊的Servlet Filter&#xff0c;它本身所做的工作并不多&#xff0c;只是将工作委托给一…...

白云区网站建设mg126/百度快照优化排名推广怎么做

简介 “const” 是constant的缩写, 表示"海枯石烂, 恒定不变, 一旦相伴, 永不变心". how to 理解 将类型去掉看 const 修饰谁, 谁就拥有了不变的特性. 举例 const int a 10; 去掉 int, 变成了 const a 10, a的值不变. int const a 10; 去掉 int, 变成了 c…...

新疆建设网站公司/职业培训机构排名前十

进程切换为什么比线程切换慢&#xff1f; 注意这里问的是为什么进程切换比线程慢&#xff0c;而不是问为什么进程比线程慢。当然这里的线程肯定指的是同一个进程中的线程。 解释下虚拟地址&#xff08;逻辑地址&#xff09;和物理地址的区别 下面这段 C 代码摘录自《操作系统…...