【算法刷题】Day10
文章目录
- 15. 三数之和
- 题干:
- 算法原理:
- 1、排序 + 暴力枚举 + 利用set 去重
- 2、排序 + 双指针
- 代码:
- 18. 18. 四数之和
- 题干:
- 算法原理:
- 1、排序 + 暴力枚举 + 利用set 去重
- 2、排序 + 双指针
- 代码:
15. 三数之和


原题链接
题干:
存在一个三元组,满足
i != j、i != k 且 j != k
nums[i] + nums[j] + nums[k] == 0
算法原理:
1、排序 + 暴力枚举 + 利用set 去重
这个方法就是先循环,用几个 for 循环暴力枚举,然后放到 HashSet 中去重
但是这个方法时间复杂度很高,达到了O(N3)
2、排序 + 双指针
(1)排序
这里进行排序是为了从前向后遍历的时候,可以更好的用双指针进行操作

(2)固定一个数 a
这个 a 必须要大于等于 0,因为题目要求三数相加等于 0
(3)在该数后面的区间内,利用“双指针算法”快速找到两个数的和等于 -a 即可

(4)处理细节问题
-
不要漏任何一个组合
在 left 和 right 向中间走的时候,找到一个数等于固定的数的负数,不能停下,继续缩小区间,寻找下一个 -
去重
由于题目要求,不能返回相同的数组,所以要求去重
这样就可以找到一种结果之后,left 和 right 指针要跳过重复元素
当使用完一次双指正算法之后,也要跳过重复元素
但要注意避免越界!!!

代码:
public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ret = new ArrayList<>();//1.排序Arrays.sort(nums);int n = nums.length;//2.利用双指针for (int i = 0; i < n;) {int left = i + 1;int right = n - 1;int target = -nums[i];if (nums[i] > 0) {break;}while (left < right) {int sum = nums[left] + nums[right];if (sum < target) {left++;}else if (sum > target) {right--;}else {ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));//缩小区间继续寻找left++;right--;while (left < right && nums[left] == nums[left-1]) {left++;}while (left < right && nums[right] == nums[right+1]) {right--;}}}i++;while (i < n && nums[i] == nums[i-1]) {i++;}}return ret;}

18. 18. 四数之和

题干:
这道题跟上面的三数之和非常相似,因此下面的解题思路也是非常相似
nums[a] + nums[b] + nums[c] + nums[d] == target
算法原理:
1、排序 + 暴力枚举 + 利用set 去重
这个算法依然是超时的,我们主要看第二种
2、排序 + 双指针
(1)排序
(2)在 a 后面的区间内,利用“三数之和”找到三个数(和上面题的方法一样),使这三个数的和等于 target - a
(3)处理细节问题
- 不漏
- 去重
代码:
public List<List<Integer>> fourSum(int[] nums, int target) {List<List<Integer>> ret = new ArrayList<>();int n = nums.length;//1.排序Arrays.sort(nums);//2.双指针for (int i = 0; i < n;) {long t1 = (long)target - nums[i];for (int j = i + 1; j < n;) {long t2 = t1 - nums[j];int left = j + 1;int right = n - 1;while (left < right) {int sum = nums[left] + nums[right];if (sum > t2) {right--;}else if (sum < t2) {left++;}else {ret.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 && nums[right] == nums[right+1]) {right--;}}}j++;while (j < n && nums[j] == nums[j-1]) {j++;}}i++;while (i < n && nums[i] == nums[i-1]) {i++;}}return ret;}

相关文章:
【算法刷题】Day10
文章目录 15. 三数之和题干:算法原理:1、排序 暴力枚举 利用set 去重2、排序 双指针 代码: 18. 18. 四数之和题干:算法原理:1、排序 暴力枚举 利用set 去重2、排序 双指针 代码: 15. 三数之和 原题链…...
SAP 如何检查已安装的SAP UI5 版本
第一个方法是直接从FLP中查看 但是部分高版本的FLP中没有这个about, 那么在当前界面可以使用:CTRL ALT SHIFT S 查看当前版本 根据此版本,去进行你的UI5的开发吧...
15、 深度学习之正向传播和反向传播
上一节介绍了训练和推理的概念,这一节接着训练和推理的概念讲一下,神经网络的正向传播和反向传播。 其实单看正向传播和反向传播这两个概念,很好理解。 正向传播(Forward Propagation)是指从输入层到输出层的数据流动过程,而反向传播(Backpropagation)是指数据从输出…...
微信小程序中复制文本
在微信小程序中,可以使用wx.setClipboardData()方法来实现复制文本内容的功能。以下是一个示例代码: // 点击按钮触发复制事件 copyText: function() {var that this;wx.setClipboardData({data: 要复制的文本内容,success: function(res) {wx.showToa…...
vue3学习--初始
...
cmake和vscode 下的cmake的使用详解(二)
第四讲: GDB 调试器 前言: GDB(GNU Debugger) 是一个用来 调试 C/C 程序 的功能强大的 调试器 ,是 Linux 系统开发 C/C 最常用的调试器 程序员可以 使用 GDB 来跟踪程序中的错误 ,从而减少程序员的工作量。 Linux 开发 C/C …...
集成开发环境 PyCharm 的安装【侯小啾python领航班系列(二)】
集成开发环境PyCharm的安装【侯小啾python领航计划系列(二)】 大家好,我是博主侯小啾, 🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹꧔ꦿ🌹…...
mysql从库设置为只读
直奔主题,mysql设置为只读后,无法增删改。 设置命令: mysql> set global read_only1; #1是只读,0是读写 mysql> show global variables like %read_only%; 以下是相关说明: 1、对于数据库读写状态…...
.NET6实现破解Modbus poll点表配置文件
📢欢迎点赞 :👍 收藏 ⭐留言 📝 如有错误敬请指正,赐人玫瑰,手留余香!📢本文作者:由webmote 原创📢作者格言:新的征程,我们面对的不仅仅是技术还有人心,人心不可测,海水不可量,唯有技术,才是深沉黑夜中的一座闪烁的灯塔 !序言 Modbus 协议是工控领域常见…...
【零基础入门Docker】Dockerfile中的USER指令以及dockerfile命令详解
✍面向读者:所有人 ✍所属专栏:Docker零基础入门专栏 目录 第 1 步:创建 Dockerfile 第 2 步:构建 Docker 镜像 第 3 步:运行 Docker 容器 第 4 步:验证输出 dockerfile命令详解 最佳实践 默认情况下…...
R语言期末考试复习二
上篇文章的后续!!!! http://t.csdnimg.cn/sqvYD 1.给向量vec1设置名为"A","B","C","D","E","F","G"。 2.将矩阵mat1的行名设置为"Row1"&#…...
golang Pool实战与底层实现
使用的go版本为 go1.21.2 首先我们写一个简单的Pool的使用代码 package mainimport "sync"var bytePool sync.Pool{New: func() interface{} {b : make([]byte, 1024)return &b}, }func main() {for j : 0; j < 10; j {obj : bytePool.Get().(*[]byte) // …...
WPF使用Prism框架批量注册Page,Window,UserControl等视图组件
前言 为了提高Prism框架下面的注册视图资源的简单性和提高后期可维护性,本文将使用prism自带的通过反射来批量注册视图资源,帮助我们快速高效的完成开发任务。 我们平常注册前端视图资源,一般都是在RegisterTypes方法里面,使用IContainerRegistry 的RegisterForNavigation…...
网络安全应急响应-Server2228(环境+解析)
网络安全应急响应 任务环境说明: 服务器场景:Server2228(开放链接)用户名:root,密码:p@ssw0rd123...
[WP] ISCTF2023 Web 部分题解
圣杯战争!!! 反序列化伪协议读取 where_is_the_flag 环境变量根目录当前目录 绕进你的心里 利用正则最大回溯绕过 easy_website or select 用双写绕过 空格用/**/绕,报错注入 wafr codesystem(ca\t /f*) webinclude 扫描得到index.bak备份文件打开为加密的代码 写…...
uniapp之Vue3配置跨域(代理)
在uni-app中,我们可以使用vue.config.js文件来配置跨域(代理)。以下是一个示例: // vue.config.js module.exports {devServer: {proxy: {/api: { // 这里填写你要代理的接口前缀,例如/apitarget: http://localhost:…...
单片机实验(三)
前言 实验一:利用定时器T1的中断控制P1.7引脚输出音频信号,启动蜂鸣器发出一段熟悉的与众不同的具有10个音节的音乐音频。 实验二:使用定时器/计数器来实现一个LCD显示年、月、日、星期 、时、分、秒的电子表,要求时和分可以方便…...
Python 2进制按位取反
根据一checksum算法需要将一些参数按位取反 例:参数 13 数字13二进制为1101 [((x)) for x in str(bin(13))] [0, b, 1, 1, 0, 1] 除去0b字符串然后按位取反得到0010 [(1^int(x)) for x in str(bin(13)).replace(0b,)] [0, 0, 1, 0]然后将得到的2进制转换成十进制…...
【用Python根据用户名和手机号码生成Hash值并创建.cs .h和xlsx文件】
用Python根据用户名和手机号码生成Hash值并创建C Sharp .cs、嵌入式.h和xlsx表格文件 用Python根据用户名和手机号码生成Hash值并创建C Sharp .cs、嵌入式.h和xlsx表格文件,主要是为每个用户创建一个pubkey,并输出C Sharp C#和嵌入式 Keil的工程文件 pub…...
<Linux>(极简关键、省时省力)《Linux操作系统原理分析之存储管理(2)》(15)
[TOC](《Linux操作系统原理分析之存储管理(2)》(15) 5 存储管理5.4 分页存储管理5.4.1 纯分页存储管理a.页(页面)和物理块(帧)b. 页面大小c. 逻辑地址结构 5.5 存储扩充技术5.5.2 交…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
