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

蓝桥杯入门即劝退(二十一)三数之和(梦破碎的地方)

欢迎===关注===点赞===评论,共同学习,共同进步!

------持续更新蓝桥杯入门系列算法实例--------

如果你也喜欢Java和算法,欢迎订阅专栏共同学习交流!

你的点赞、关注、评论、是我创作的动力!

-------希望我的文章对你有所帮助--------

💪😳👍

一、题目描述

  给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]

解释:

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。

示例 2:

输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。

示例 3:

输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。

二、解题思路

1、对于求三数之和需要注意的是返回的是一个元组,且不能重复,因此测试用例必然会出现许多重复的结果,需要在过程中剔除。
2、首先即使用Arrays数组内置排序模块进行升序排序,要求a+b+c=0,且a<b<c;
即a<0,a+b>0,或a+b>0,c<0;
且当a>0时,即不可能有sum为0,直接return掉。
3、采用双指针法,类似于二分查找,将num[0]设置为a,b则是其后一个元素,c为最大的元素。
4、开始二分遍历,首先剔除掉a的重复元素
5、计算sum和,如果sum>0,说明值过大,则right指针左移使得整体值减小以接近0;
      如果sum<0,即值过小,要将left右移动以接近0;
6、当sum恰好为0时,将三个元素加入到列表中;
7、再次对b、c重复值进行剔除,且指针也要相应的移动实现剔除
8、最后返回结果即可。

三、代码实现

public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result=new ArrayList<>();Arrays.sort(nums);int sum=0;for (int i=0;i< nums.length;i++){if (nums[i]>0)return result;if (i>0&&nums[i]==nums[i-1])continue;//跳过即剔除int left=i+1;//相当于左边界int rigth= nums.length-1;//相当于右边界while (rigth>left){sum=nums[i]+nums[left]+nums[rigth];if (sum>0)rigth--;else if (sum<0)left++;else {result.add(Arrays.asList(nums[i],nums[left],nums[rigth]));//加入列表while (rigth>left&&nums[rigth]==nums[rigth-1]) rigth--;//剔除重复的cwhile (rigth>left&&nums[left]==nums[left+1]) left++;//剔除重复的brigth--;//再次移动left++;}}}return result;}

发文不易,恳请大佬们高抬贵手!
点赞:随手点赞是种美德,是大佬们对于本人创作的认可!
评论:往来无白丁,是你我交流的的开始!
收藏:愿君多采撷,是大佬们对在下的赞赏!

相关文章:

蓝桥杯入门即劝退(二十一)三数之和(梦破碎的地方)

欢迎关注点赞评论&#xff0c;共同学习&#xff0c;共同进步&#xff01;------持续更新蓝桥杯入门系列算法实例--------如果你也喜欢Java和算法&#xff0c;欢迎订阅专栏共同学习交流&#xff01;你的点赞、关注、评论、是我创作的动力&#xff01;-------希望我的文章对你有所…...

element 下拉框支持搜索并输入

前言 下拉框对于开发来说再常见不过了&#xff0c;也是界面设计中的常用组件&#xff0c;在部分使用场景下&#xff0c;我们需要做到下拉框可以选择的同时&#xff0c;支持搜素和输入&#xff0c;以 element 的下拉框组件为例&#xff0c;当我们同时设置属性让其支持搜素和输入…...

JVM详解——垃圾回收

如果有兴趣了解更多相关内容的话&#xff0c;可以看看我的个人网站&#xff1a;耶瞳空间 GC&#xff1a;垃圾收集(Gabage Collection)&#xff0c;内存处理是编程人员容易出现问题的地方&#xff0c;忘记或者错误的内存。不当的回收可能会导致程序或系统的不稳定甚至崩溃&…...

spring之集成Mybatis

文章目录一、实现步骤1、准备数据库表2、在IDEA中创建一个模块&#xff0c;并引入依赖3、基于三层架构实现4、编写pojo5、编写mapper接口6、编写mapper配置文件7、编写service接口和service接口的实现类8、编写jdbc.properties配置文件9、编写mybatis-config.xml配置文件10、编…...

【面试宝典】准备面试了~集合

1、ArrayList和linkedList的区别 它们都是继承自 Collection。 ArrayList 是基于数组的&#xff0c;在使用查询的时候效率比较高&#xff0c;但删除效率却非常低&#xff0c;因为它需要重新排数组中的所有数据。 LinkList底层是一个双链表&#xff0c;在添加和删除元素时更好…...

华为OD机试真题Python实现【GPU 调度】真题+解题思路+代码(20222023)

GPU 调度 题目 为了充分发挥 GPU 算力, 需要尽可能多的将任务交给 GPU 执行, 现在有一个任务数组, 数组元素表示在这1s内新增的任务个数, 且每秒都有新增任务, 假设 GPU 最多一次执行n个任务, 一次执行耗时1s, 在保证 GPU 不空闲的情况下,最少需要多长时间执行完成。…...

gcc编译C源程序

一、安装 在Linux下&#xff0c;一般使用gcc或arm-linux-gcc交叉编译器来编译程序。在Ubuntu环境下&#xff0c;我们可以使用以下apt-get命令来安装这些编译程序。 apt-get install gcc apt-get install gcc-arm-linux-gnueabi 安装完毕后&#xff0c;使用以下命令查看编译器…...

Tina_Linux_各平台多媒体格式_支持列表_new

Tina Linux 各平台多媒体格式支持列表 1 概述 1.1 编写目的 本文档将介绍Allwinner Tina Linux 系统各个芯片平台支持的多媒体格式&#xff0c;旨在帮助软件开发工程师、技术支持工程师查找各芯片平台支持哪些多媒体格式。 1.2 适用范围 Tina Linux v3.5 及以上版本。 1.…...

归并排序及其应用

归并排序算法基于分而治之的概念&#xff0c;具体来说就是遍历一棵树&#xff0c;归并的过程是一个后序执行的动作。 由于我们知道每个子部分在合并后都是有序的&#xff0c;我们可以利用这个特性来解决一些问题。 上图可视化了merge sort algorithm的过程&#xff0c;我们很容…...

【PAT甲级题解记录】1007 Maximum Subsequence Sum (25 分)

【PAT甲级题解记录】1007 Maximum Subsequence Sum (25 分) 前言 Problem&#xff1a;1007 Maximum Subsequence Sum (25 分) Tags&#xff1a;DP Difficulty&#xff1a;剧情模式 想流点汗 想流点血 死而无憾 Address&#xff1a;1007 Maximum Subsequence Sum (25 分) 问题描…...

华为OD机试真题Python实现【 最小叶子节点】真题+解题思路+代码(20222023)

最小叶子节点 题目 二叉树也可以用数组来存储, 给定一个数组,树的根节点的值储存在下标1, 对于储存在下标n的节点,他的左子节点和右子节点分别储存在下标2*n和2*n+1, 并且我们用-1代表一个节点为空, 给定一个数组存储的二叉树, 试求从根节点到最小的叶子节点的路径, …...

mars3d动态轨迹DynamicRoamLine,如何获取实时运⾏的经纬度

问题 1.期望 实现 实时显示经纬度、⾼度&#xff0c;做电⼦围栏报警判断 2.第⼀步就是要&#xff0c;获取实时运⾏的经纬度信息、⾼度信息&#xff0c;然后通过算法做电⼦围栏判断 3.使⽤了参数getOverPositions&#xff0c;发现返回的不是经纬度 相关链接 http://mars3d.cn//e…...

jvm常识

Jvm工作原理学习笔记0126一、JVM的生命周期1.JVM实例对应了一个独立运行的java程序它是进程级别a)启动。启动一个Java程序时&#xff0c;一个JVM实例就产生了&#xff0c;任何一个拥有public static void main(String[] args)函数的class都可以作为JVM实例运行的起点b)运行。ma…...

PHP部署、nginx与PHP的整合、PHP动态添加模块

文章目录前言一、基本知识1.php介绍2.PHP能做什么3.web工作原理4.PHP脚本主要用于领域5.php其他相关信息6.memcache介绍二、php的源码安装1.php安装2.php配置三、nginx与php整合四、php动态扩展模块&#xff08;memcache模块&#xff09;前言 一、基本知识 1.php介绍 官方下载…...

SpringCloud与SpringBoot的版本对应

一、SpringCloud与SpringBoot的版本对应 SpringCloud版本 SpringBoot版本 2021.0.1-SNAPSHOT Spring Boot >2.6.4-SNAPSHOT and <2.7.0-M1 2021.0.0 Spring Boot >2.6.1 and <2.6.4-SNAPSHOT 2021.0.0-RC1 Spring Boot >2.6.0-RC1 and <2.6.1 2021.0.0-M3 Sp…...

华为OD机试题,用 Java 解【N 进制减法】问题

最近更新的博客 华为OD机试 - 猴子爬山 | 机试题算法思路 【2023】华为OD机试 - 分糖果(Java) | 机试题算法思路 【2023】华为OD机试 - 非严格递增连续数字序列 | 机试题算法思路 【2023】华为OD机试 - 消消乐游戏(Java) | 机试题算法思路 【2023】华为OD机试 - 组成最大数…...

Linux->进程概念于基本创建

1. 进程基本概念 当一个可执行程序被加载到内存当中&#xff0c;并由操作系统将其管理起来&#xff0c;此时这个程序就被称之为进程。也就是下方的&#xff1a; 程序的一个执行实例&#xff0c;正在执行的程序等 担当分配系统资源&#xff08;CPU时间&#xff0c;内存&#xff…...

【MySQL】5.7版本解压安装配置

前言 之所以使用解压版本&#xff0c;而不使用exe安装&#xff0c;因为exe的安装方式删除过于麻烦&#xff01;&#xff01;&#xff01; 如果安装MySQL过程中&#xff0c;出错了或者想重新在来一把&#xff0c;删除mysql服务即可 sc delete mysql # 删除已经安装好的Mysql&a…...

c++类对象数据成员和虚函数的内存布局

一直想搞清楚类对象的数据成员和虚函数的内存布局&#xff0c;今天刚好有时间&#xff0c;所以就写了个demo查看了一下具体的内存布局情况&#xff08;使用的编译器为微软的&#xff09;。下面是自己demo的代码&#xff1a;#include <iostream> #include <windows.h&g…...

Python 模块和包

1. 模块和包 **容器&#xff1a;**列表、元组、字符串、字典等&#xff0c;对数据的封装**函数&#xff1a;**对语句的封装**类&#xff1a;**对方法和属性的封装&#xff0c;即对函数和数据的封装 而模块&#xff08;module&#xff09;就是个程序&#xff0c;一个.py 文件&…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...