代码随想录算法训练营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循环,先用HashMap存储所有第一组for循环出现的和的次数。再进行第二组for循环,每一次得出的和判断其负数是否在map的key中,如果存在,就加上这个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的宏编程中,宏可以接受多种类型的参数,称为“指示符”。这些指示符帮助宏识别不同类型的代码片段,并相应地处理它们。 这里列出全部指示符: 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)
缓冲流 字节缓冲流 利用字节缓冲区拷贝文件,一次读取一个字节: public class test {public static void main(String [] args) throws IOException {//利用字节缓冲区来拷贝文件BufferedInputStream bisnew BufferedInputStream(new FileInputStream(&…...
【docker】docker启动bitnami/mysql
说明:-v 宿主机目录:docker容器目录,-p 同理 注意:/opt/bitnami/mysql/conf/bitnami 目录自定义conf的目录,不能使用原有的/opt/bitnami/mysql/conf 目录。 容器启动后可在宿主机的/宿主/mysql8.0/conf,添加my_custom.…...
边缘计算、云计算、雾计算在物联网中的作用
边缘计算和雾计算不像云那样广为人知,但可以为企业和物联网公司提供很多帮助。这些网络解决了物联网云计算服务无法解决的许多问题,并使分散的数据存储适应特定的需求。让我们分别研究一下边缘计算、雾计算和云计算的优势。 雾计算的好处 低延迟。雾网络…...
【c语言】探索内存函数
探索内存函数 memcpy函数memmove函数memset函数memcmp函数: memcpy函数 memcpy函数声明: void * memcpy ( void * destination, const void * source, size_t num );将source空间下的num个字符复制到dest中去 函数的使用: 将字符数组a的5字…...

day46 完全背包理论基础 518. 零钱兑换 II 377. 组合总和 Ⅳ
完全背包理论基础 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品都有无限个(也就是可以放入背包多次),求解将哪些物品装入背包里物品价值总和最大。 01背包内嵌的循环是从…...

【linux】运维-基础知识-认知hahoop周边
1. HDFS HDFS(Hadoop Distributed File System)–Hadoop分布式文件存储系统 源自于Google的GFS论文,HDFS是GFS的克隆版 HDFS是Hadoop中数据存储和管理的基础 他是一个高容错的系统,能够自动解决硬件故障,eg:…...

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

Flutter 验证码输入框
前言: 验证码输入框很常见:处理不好 bug也会比较多 想实现方法很多,这里列举一种完美方式,完美兼容 软键盘粘贴方式 效果如下: 之前使用 uniapp 的方式实现过一次 两种方式(原理相同)࿱…...
如何从0到设计一个CRM系统
什么是CRM 设计开始之前,先来了解一下什么是CRM。CRM(Customer Relationship Management)是指通过建立和维护与客户的良好关系,达到满足客户需求、提高客户满意度、增加业务收入的一种管理方法和策略。CRM涉及到跟踪和管理客户的所…...

Numba 的 CUDA 示例 (2/4):穿针引线
本教程为 Numba CUDA 示例 第 2 部分。 按照本系列从头开始使用 Python 学习 CUDA 编程 介绍 在本系列的第一部分中,我们讨论了如何使用 GPU 运行高度并行算法。高度并行任务是指任务完全相互独立的任务,例如对两个数组求和或应用任何元素函数。 在本教…...
项目的各个阶段如何编写标准的Git commit消息
标准提交消息格式 一个标准的提交消息应包括三部分:标题(summary)、正文(description)和脚注(footer)。 1. 标题(Summary) 简洁明了,不超过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的结构(ASN.1) RSAPrivateKey :: SEQUENCE { version Version, modulus INTEGER, -- n publicExponent INTEGER, -- e privateExponent INTEGER, -- d prime1 INTEGER, -- …...

【Linux】Linux基本指令2
目录 1.man指令(重要): 2.echo指令 3.cp指令(重要): 4.mv指令 5.cat指令/echo指令重定向 6.more指令 7.less指令(重要) 8.head指令 9.tail指令 我们接着上一篇:h…...

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

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

【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
Java + Spring Boot + Mybatis 实现批量插入
在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法:使用 MyBatis 的 <foreach> 标签和批处理模式(ExecutorType.BATCH)。 方法一:使用 XML 的 <foreach> 标签ÿ…...
MySQL JOIN 表过多的优化思路
当 MySQL 查询涉及大量表 JOIN 时,性能会显著下降。以下是优化思路和简易实现方法: 一、核心优化思路 减少 JOIN 数量 数据冗余:添加必要的冗余字段(如订单表直接存储用户名)合并表:将频繁关联的小表合并成…...
C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)
名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...
LRU 缓存机制详解与实现(Java版) + 力扣解决
📌 LRU 缓存机制详解与实现(Java版) 一、📖 问题背景 在日常开发中,我们经常会使用 缓存(Cache) 来提升性能。但由于内存有限,缓存不可能无限增长,于是需要策略决定&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# 如果存在࿰…...