当前位置: 首页 > 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…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

sipsak:SIP瑞士军刀!全参数详细教程!Kali Linux教程!

简介 sipsak 是一个面向会话初始协议 (SIP) 应用程序开发人员和管理员的小型命令行工具。它可以用于对 SIP 应用程序和设备进行一些简单的测试。 sipsak 是一款 SIP 压力和诊断实用程序。它通过 sip-uri 向服务器发送 SIP 请求&#xff0c;并检查收到的响应。它以以下模式之一…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...

上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式

简介 在我的 QT/C 开发工作中&#xff0c;合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式&#xff1a;工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...