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

代码随想录算法训练营Day7|454.四数相加II、 383. 赎金信、15. 三数之和、 18. 四数之和

454.四数相加II

四个数组分成两组进行for循环,先用HashMap存储所有第一组for循环出现的和的次数。再进行第二组for循环,每一次得出的和判断其负数是否在map的key中,如果存在,就加上这个value。

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();for(int num1:nums1){for(int num2:nums2){if(map.containsKey(num1+num2)){int a = map.get(num1+num2);map.put(num1+num2,++a);}else{map.put(num1+num2,1);}}}int total = 0;for(int num3:nums3){for(int num4:nums4){if(map.containsKey(-(num3+num4))){total += map.get(-(num3+num4));}}}return total;}
}

383. 赎金信

和有效的字母异位词那道题目类似

class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] record = new int[26];for(int i = 0;i < magazine.length();i++){record[magazine.charAt(i)-'a']++;}for(int i = 0;i < ransomNote.length();i++){record[ransomNote.charAt(i)-'a']--;}for(int r:record){if(r < 0) return false;}return true;}
}

15. 三数之和

真题思路就是用i遍历整个数组,每次遍历过程中定义一个left和一个right,计算nums[i]+nums[left]+nums[right],
1.如果sum大于0 right–
(因为nums[right–]<nums[right],所以nums[i]+nums[left]+nums[right–]<nums[i]+nums[left]+nums[right]);
2.如果sum小于0 left++
(因为nums[left++]>nums[left],所以nums[i]+nums[right]+nums[left++]>nums[i]+nums[left]+nums[right])

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> resList = new ArrayList<List<Integer>>();Arrays.sort(nums);if(nums[0] > 0 || nums[nums.length-1] < 0 || nums.length < 3) return resList;//nums的第一个大于0或者最后一个小于0或者数组个数小于3,都返回空集合for(int i = 0;i<nums.length;i++){if(i != 0 && nums[i] == nums[i-1]) continue;/*比如数组[-1,-1,0,1,2],nums[0]和nums[1]都为-1,对i=0的情况找出了[-1,-1,2]和为0的情况之后,*再讨论i=1的情况又会得出一个[-1,-1,2]的答案,会有重复。但是不能nums[i] == nums[i+1]这样向后对比,*因为nums[0]=nums[1],直接跳过i=0,就忽略了[-1,-1,2]这种情况。*/int left = i+1;int right = nums.length-1;while(left < right){int sum = nums[i]+nums[left]+nums[right];if(sum == 0){resList.add(Arrays.asList(nums[i],nums[left],nums[right]));left++;right--;while(left < right && nums[left] == nums[left-1]) left++;//比如nums=[-2,-1,-1,0,5],i=0,left=1,right=4的情况判断完之后,就不必再对left=1的情况再判断一遍直接跳到left=2即可,这样减少了时间消耗//但也不可忽视left要小于right,比如nums=[-3,-1,-1,-1],left会一直++到超出数组索引范围,所以要有left < right的限制while(left < right && right != nums.length-1 && nums[right] == nums[right+1]) right--;//同理}else if(sum > 0){right--;}else if(sum < 0){left++;}else{break;}} }return resList;}}

18. 四数之和

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

相关文章:

代码随想录算法训练营Day7|454.四数相加II、 383. 赎金信、15. 三数之和、 18. 四数之和

454.四数相加II 四个数组分成两组进行for循环&#xff0c;先用HashMap存储所有第一组for循环出现的和的次数。再进行第二组for循环&#xff0c;每一次得出的和判断其负数是否在map的key中&#xff0c;如果存在&#xff0c;就加上这个value。 class Solution {public int four…...

编译器屏障概述

文章目录 1. 前言2. 编译器内存屏障2.1 编译器内存访问重排序规则2.2 编译器屏障的几种形式2.2.1 显式编译器屏障2.2.2 隐式编译器屏障2.2.3 硬件内存屏障充当编译屏障2.2.4 编程语言内存模型提供的编译屏障 2.3 编译器内存屏障实例2.3.1 Linux spinlock 3. 结语4. 参考资料 1.…...

RUST宏编程入门

宏指示符 在Rust的宏编程中&#xff0c;宏可以接受多种类型的参数&#xff0c;称为“指示符”。这些指示符帮助宏识别不同类型的代码片段&#xff0c;并相应地处理它们。 这里列出全部指示符&#xff1a; blockexpr 用于表达式ident 用于变量名或函数名itemliteral 用于字面常…...

linux安装srs

获取srs cd /opt git clone -b 4.0release https://gitee.com/ossrs/srs.git cd srs/trunk 启动srs ./objs/srs -c conf/srs.conf ./etc/init.d/srs status 访问http://192.168.220.146:8080/出现下方图片说明安装成功 点击进入SRS控制台看到下方图片...

IO流(2)

缓冲流 字节缓冲流 利用字节缓冲区拷贝文件&#xff0c;一次读取一个字节&#xff1a; public class test {public static void main(String [] args) throws IOException {//利用字节缓冲区来拷贝文件BufferedInputStream bisnew BufferedInputStream(new FileInputStream(&…...

【docker】docker启动bitnami/mysql

说明&#xff1a;-v 宿主机目录:docker容器目录&#xff0c;-p 同理 注意&#xff1a;/opt/bitnami/mysql/conf/bitnami 目录自定义conf的目录&#xff0c;不能使用原有的/opt/bitnami/mysql/conf 目录。 容器启动后可在宿主机的/宿主/mysql8.0/conf&#xff0c;添加my_custom.…...

边缘计算、云计算、雾计算在物联网中的作用

边缘计算和雾计算不像云那样广为人知&#xff0c;但可以为企业和物联网公司提供很多帮助。这些网络解决了物联网云计算服务无法解决的许多问题&#xff0c;并使分散的数据存储适应特定的需求。让我们分别研究一下边缘计算、雾计算和云计算的优势。 雾计算的好处 低延迟。雾网络…...

【c语言】探索内存函数

探索内存函数 memcpy函数memmove函数memset函数memcmp函数&#xff1a; memcpy函数 memcpy函数声明&#xff1a; void * memcpy ( void * destination, const void * source, size_t num );将source空间下的num个字符复制到dest中去 函数的使用&#xff1a; 将字符数组a的5字…...

day46 完全背包理论基础 518. 零钱兑换 II 377. 组合总和 Ⅳ

完全背包理论基础 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]&#xff0c;得到的价值是value[i] 。每件物品都有无限个&#xff08;也就是可以放入背包多次&#xff09;&#xff0c;求解将哪些物品装入背包里物品价值总和最大。 01背包内嵌的循环是从…...

【linux】运维-基础知识-认知hahoop周边

1. HDFS HDFS&#xff08;Hadoop Distributed File System&#xff09;–Hadoop分布式文件存储系统 源自于Google的GFS论文&#xff0c;HDFS是GFS的克隆版 HDFS是Hadoop中数据存储和管理的基础 他是一个高容错的系统&#xff0c;能够自动解决硬件故障&#xff0c;eg&#xff1a…...

Python自动实时查询预约网站的剩余名额并在有余额时发邮件提示

本文介绍基于Python语言&#xff0c;自动、定时监测某体检预约网站中指定日期的体检余额&#xff0c;并在有体检余额时自动给自己发送邮件提醒的方法。 来到春招末期&#xff0c;很多单位进入了体检流程。其中&#xff0c;银行&#xff08;尤其是四大行&#xff09;喜欢“海检”…...

Flutter 验证码输入框

前言&#xff1a; 验证码输入框很常见&#xff1a;处理不好 bug也会比较多 想实现方法很多&#xff0c;这里列举一种完美方式&#xff0c;完美兼容 软键盘粘贴方式 效果如下&#xff1a; 之前使用 uniapp 的方式实现过一次 两种方式&#xff08;原理相同&#xff09;&#xff1…...

如何从0到设计一个CRM系统

什么是CRM 设计开始之前&#xff0c;先来了解一下什么是CRM。CRM&#xff08;Customer Relationship Management&#xff09;是指通过建立和维护与客户的良好关系&#xff0c;达到满足客户需求、提高客户满意度、增加业务收入的一种管理方法和策略。CRM涉及到跟踪和管理客户的所…...

Numba 的 CUDA 示例 (2/4):穿针引线

本教程为 Numba CUDA 示例 第 2 部分。 按照本系列从头开始使用 Python 学习 CUDA 编程 介绍 在本系列的第一部分中&#xff0c;我们讨论了如何使用 GPU 运行高度并行算法。高度并行任务是指任务完全相互独立的任务&#xff0c;例如对两个数组求和或应用任何元素函数。 在本教…...

项目的各个阶段如何编写标准的Git commit消息

标准提交消息格式 一个标准的提交消息应包括三部分&#xff1a;标题&#xff08;summary&#xff09;、正文&#xff08;description&#xff09;和脚注&#xff08;footer&#xff09;。 1. 标题&#xff08;Summary&#xff09; 简洁明了&#xff0c;不超过50个字符。使用…...

Python课设-学生信息管理系统

一、效果展示图 二、前端代码 1、HTML代码 <1>index.html <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0">…...

openssl 常用命令demo

RSA Private Key的结构&#xff08;ASN.1&#xff09; RSAPrivateKey :: SEQUENCE { version Version, modulus INTEGER, -- n publicExponent INTEGER, -- e privateExponent INTEGER, -- d prime1 INTEGER, -- …...

【Linux】Linux基本指令2

目录 1.man指令&#xff08;重要&#xff09;&#xff1a; 2.echo指令 3.cp指令&#xff08;重要&#xff09;&#xff1a; 4.mv指令 5.cat指令/echo指令重定向 6.more指令 7.less指令&#xff08;重要&#xff09; 8.head指令 9.tail指令 我们接着上一篇&#xff1a;h…...

springboot+vue+mybatis博物馆售票系统+PPT+论文+讲解+售后

如今社会上各行各业&#xff0c;都喜欢用自己行业的专属软件工作&#xff0c;互联网发展到这个时候&#xff0c;人们已经发现离不开了互联网。新技术的产生&#xff0c;往往能解决一些老技术的弊端问题。因为传统博物馆售票系统信息管理难度大&#xff0c;容错率低&#xff0c;…...

java—MyBatis框架

简介 什么是 MyBatis&#xff1f; MyBatis 是一款优秀的持久层框架&#xff0c;它支持自定义 SQL、存储过程以及高级映射。MyBatis 免除了几乎所有的 JDBC 代码以及设置参数和获取结果集的工作。MyBatis 可以通过简单的 XML 或注解来配置和映射原始类型、接口和 Java POJO&…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

PostgreSQL——环境搭建

一、Linux # 安装 PostgreSQL 15 仓库 sudo dnf install -y https://download.postgresql.org/pub/repos/yum/reporpms/EL-$(rpm -E %{rhel})-x86_64/pgdg-redhat-repo-latest.noarch.rpm# 安装之前先确认是否已经存在PostgreSQL rpm -qa | grep postgres# 如果存在&#xff0…...