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

LeetCode15.三数之和

题目链接:15. 三数之和 - 力扣(LeetCode)

1.常规解法(会超时)

由于这道题需要排除相同的三元组,则可以先将目标数组从小到大排序,再遍历数组找到每个符合条件的三元组,若结果中不包含该三元组,就将该结果添加到目标结果中,代码如下:

    public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ret = new ArrayList<>();Arrays.sort(nums);int n = nums.length;for (int i = 0; i < n - 2; i++) {for (int j = i + 1; j < n - 1; j++) {for (int k = j + 1; k < n; k++) {if (nums[i] + nums[j] + nums[k] == 0) {List<Integer> list = new ArrayList<>();list.add(nums[i]);list.add(nums[j]);list.add(nums[k]);if (!ret.contains(list)) {ret.add(list);}}}}}return ret;}

2. 双指针算法

和常规解法一样,我们要先将目标数组从小到大排序,由于要求三数之和等于0,我们可以先固定一个数,只需找到剩下的哪两个数与这个数的和为0,再定义一个顺序表存放三元组。

定义三个指针left,right,p,先将p固定在最后一个数,left在第一个数的位置,right在倒数第二个数的位置,接下来在每一轮循环中,保持p不动,只要移动left和right即可。

当nums[left] + nums[right] + nums[p] > 0,由单调性知,若保持right不动,left右边的数均大于left指向的数,导致三数之和只会越加越大(数组是从大到小排序的),这时就要将right向左移动一位;当nums[left] + nums[right] + nums[p] < 0,由单调性知,若保持left不动,right左边的数均小于right指向的数,导致三个数之和会越加越小,这是就要将left向右移动一位;当nums[left] + nums[right] + nums[p] == 0,就要将这个结果添加到顺序表中,由于最后的结果不允许出现相同的三元组,这时就要去重。

去重:若使用contains判断三元组是否重复,代码就会超时,这时我们就要在nums[left] + nums[right] + nums[p] == 0时,将与left和right指向的数的相同的数去掉,由于这个数组是有序的,那么相同的数就会聚集在一起,只需要使用while循环去重即可;相同的,当left与right相遇时,第一轮循环结束,也去要进行去重操作,将与p指向的数相同的数跳过即可。

优化:当p指向的元素小于0时,由单调性知,p左边的元素均小于0,就不存在三个数之和为0的情况,直接返回结果即可。

流程图与代码如下:

    public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> ret = new ArrayList<>();Arrays.sort(nums);int n = nums.length;int p = n - 1;while (p > 1) {int left = 0;int right = p - 1;if (nums[p] < 0) {return ret;}while (left < right) {if (nums[left] + nums[right] + nums[p] < 0) {left++;} else if (nums[left] + nums[right] + nums[p] > 0) {right--;} else {List<Integer> list = new ArrayList<>();list.add(nums[left]);list.add(nums[right]);list.add(nums[p]);ret.add(list);int numLeft = nums[left++];while (nums[left] == numLeft && left < right) {left++;}int numRight = nums[right--];while (nums[right] == numRight && left < right) {right--;}}}int numP = nums[p--];while (nums[p] == numP && p > 1) {p--;}}return ret;}

 希望大家积极指出不足之处

相关文章:

LeetCode15.三数之和

题目链接&#xff1a;15. 三数之和 - 力扣&#xff08;LeetCode&#xff09; 1.常规解法&#xff08;会超时&#xff09; 由于这道题需要排除相同的三元组&#xff0c;则可以先将目标数组从小到大排序&#xff0c;再遍历数组找到每个符合条件的三元组&#xff0c;若结果中不包…...

SpringBoot3.3 优雅启停定时任务

定时任务是非常常见的功能,在一个复杂的应用程序中,如何优雅地管理这些定时任务的启动与停止尤为重要。 Spring Boot 提供了强大的任务调度支持,通过@Scheduled注解可以轻松地创建定时任务,并且可以通过配置来灵活地管理这些任务的执行环境。在本文中,我们将深入探讨如何…...

数据结构之二叉搜索树(key模型与key_value模型)

二叉搜索树&#xff08;key模型与key_value模型&#xff09; 1. ⼆叉搜索树的概念2. ⼆叉搜索树的性能分析3. ⼆叉搜索树的插⼊4. ⼆叉搜索树的查找5. ⼆叉搜索树的删除6. ⼆叉搜索树的实现代码7. ⼆叉搜索树key和key/value使⽤场景7.1 key搜索场景&#xff1a;7.2 key/value搜…...

图说几何学2300年重大错误:附着在直线z上的直线段必是z的一部分

黄小宁 用泡沫塑料和油漆制成的铅球与真正的铅球&#xff0c;两者有不同的内部形状。同样&#xff0c;数学有长度相同但内部形状不同的伪≌直线段。 几何学有史2300年来一直认定附着在直线z上的直线段一定是z的一部分。其实这是2300年肉眼直观错觉——百年病态集论的症结。 …...

汽车网关(GW)技术分析

一、引言 在现代汽车电子系统中&#xff0c;汽车网关&#xff08;Gateway&#xff0c;简称 GW&#xff09;扮演着至关重要的角色。随着汽车电子技术的不断发展&#xff0c;汽车内部的电子控制单元&#xff08;Electronic Control Unit&#xff0c;简称 ECU&#xff09;数量不断…...

Telnet命令详解:安装、用法及应用场景解析

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storm…...

C++之LIST模拟实现(代码纯享版)

目录 文章目录 前言 一、代码 总结 前言 本文主要展示了模拟List的代码实现 一、代码 #pragma once #include<iostream> #include<assert.h> using namespace std; namespace zlh {template<class T>struct list_node{T _data;list_node<T>* _next;l…...

华为OD机试 - 括号匹配 - 栈(Python/JS/C/C++ 2024 E卷 100分)

华为OD机试 2024E卷题库疯狂收录中&#xff0c;刷题点这里 专栏导读 本专栏收录于《华为OD机试真题&#xff08;Python/JS/C/C&#xff09;》。 刷的越多&#xff0c;抽中的概率越大&#xff0c;私信哪吒&#xff0c;备注华为OD&#xff0c;加入华为OD刷题交流群&#xff0c;…...

打破欧美10年芯片垄断,杨振宁教授关门弟子,仅用三年创造奇迹

有这么一位超级厉害的中国人&#xff0c;硬是把欧美那边垄断了十年的芯片技术给“撬”开了&#xff01;说起来&#xff0c;这才是我们该追的真正明星啊&#xff01;那么&#xff0c;这位大神到底是谁&#xff1f;又是怎么让欧美芯片圈儿里的人听到她的名字就心里发怵的呢&#…...

OpenCV视频I/O(20)视频写入类VideoWriter之用于将图像帧写入视频文件函数write()的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 cv::VideoWriter::write() 函数用于将图像帧写入视频文件。 该函数/方法将指定的图像写入视频文件。图像的大小必须与打开视频编写器时指定的大…...

音视频入门基础:FLV专题(14)——FFmpeg源码中,解码Script Tag的实现

一、引言 在《音视频入门基础&#xff1a;FLV专题&#xff08;9&#xff09;——Script Tag简介》中对Script Tag进行了简介&#xff0c;本文讲述FFmpeg源码中是怎样解码FLV文件的Script Tag&#xff0c;拿到里面的信息。 二、flv_read_packet函数 从《音视频入门基础&#x…...

小猿口算APP脚本(协议版)

小猿口算是一款专注于数学学习的教育应用,主要面向小学阶段的学生。它提供多种数学练习和测试,包括口算、速算、应用题等。通过智能化的题目生成和实时批改功能,帮助学生提高数学计算能力。此外,它还提供详细的学习报告和分析,帮助家长和教师了解学生的学习进度和薄弱环节…...

【长文梳理webserver核心】核心类篇

前言 有三个核心组件支撑一个reactor实现 [持续] 的 [监听] 一组fd&#xff0c;并根据每个fd上发生的事件 [调用] 相应的处理函数。这三个组件就是 EventLoop 、Channel 以及 Poller 三个类&#xff0c;其中 EventLoop 可以看作是对业务线程的封装&#xff0c;而 Channel 可以看…...

[实用工具]Docker安装nextcloud实现私有云服务和onlyoffice

Nextcloud是一款开源的云存储和协作平台&#xff0c;允许用户在自己的服务器上存储和访问文件&#xff0c;同时提供强大的协作工具。它可以替代商业云存储服务&#xff0c;让用户拥有完全控制和自主管理自己的数据。 Nextcloud支持文件上传和下载&#xff0c;可以通过Web界面、…...

基于STM32设计的生猪健康检测管理系统(NBIOT+OneNet)(240)

文章目录 一、前言1.1 项目介绍【1】项目开发背景【2】设计实现的功能【3】项目硬件模块组成1.2 设计思路1.3 项目开发背景【1】选题的意义【2】可行性分析【3】参考文献【4】项目背景【5】摘要1.4 开发工具的选择【1】设备端开发【2】上位机开发1.5 系统功能总结1.6 系统框架图…...

springboot kafka多数据源,通过配置动态加载发送者和消费者

前言 最近做项目&#xff0c;需要支持kafka多数据源&#xff0c;实际上我们也可以通过代码固定写死多套kafka集群逻辑&#xff0c;但是如果需要不修改代码扩展呢&#xff0c;因为kafka本身不处理额外逻辑&#xff0c;只是起到削峰&#xff0c;和数据的传递&#xff0c;那么就需…...

【华为】基于华为交换机的VLAN配置与不同VLAN间通信实现

划分VLAN&#xff08;虚拟局域网&#xff09;主要作用&#xff1a; 一、提高网络安全性 广播域隔离访问控制增强 二、优化网络性能 减少网络拥塞提高网络可管理性 sysytem-view #进入系统视图配置参数 vlan batch 10 20 #批量创建vlan LSW3: int g0/0/1 port…...

力扣题11~20

题11&#xff08;中等&#xff09;&#xff1a; 思路&#xff1a; 这种题目第一眼就是双循环&#xff0c;但是肯定不行滴&#xff0c;o(n^2)这种肯定超时&#xff0c;很难接受。 所以要另辟蹊径&#xff0c;我们先用俩指针&#xff08;标志位&#xff09;在最左端和最右端&am…...

更美观的HTTP性能监测工具:httpstat

reorx/httpstat是一个旨在提供更美观和详细HTTP请求统计信息的cURL命令行工具&#xff0c;它能够帮助开发者和运维人员深入理解HTTP请求的性能和状态。 1. 基本概述 项目地址&#xff1a;https://github.com/reorx/httpstat语言&#xff1a;该工具主要是以Python编写&#xff…...

在2024 VDC,听一曲“蓝心智能”的江河协奏

作为科技从业者&#xff0c;我们每年参加的终端产品发布会和开发者大会&#xff0c;少则几十场。说每一场都别有新意&#xff0c;那自然是不可能的&#xff0c;但每次去vivo的活动现场&#xff0c;总能给我耳目一新的感觉。 雨果说过&#xff0c;音乐可以表达难以用语言描述&am…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

智能职业发展系统:AI驱动的职业规划平台技术解析

智能职业发展系统&#xff1a;AI驱动的职业规划平台技术解析 引言&#xff1a;数字时代的职业革命 在当今瞬息万变的就业市场中&#xff0c;传统的职业规划方法已无法满足个人和企业的需求。据统计&#xff0c;全球每年有超过2亿人面临职业转型困境&#xff0c;而企业也因此遭…...