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.三数之和
题目链接:15. 三数之和 - 力扣(LeetCode) 1.常规解法(会超时) 由于这道题需要排除相同的三元组,则可以先将目标数组从小到大排序,再遍历数组找到每个符合条件的三元组,若结果中不包…...

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

数据结构之二叉搜索树(key模型与key_value模型)
二叉搜索树(key模型与key_value模型) 1. ⼆叉搜索树的概念2. ⼆叉搜索树的性能分析3. ⼆叉搜索树的插⼊4. ⼆叉搜索树的查找5. ⼆叉搜索树的删除6. ⼆叉搜索树的实现代码7. ⼆叉搜索树key和key/value使⽤场景7.1 key搜索场景:7.2 key/value搜…...
图说几何学2300年重大错误:附着在直线z上的直线段必是z的一部分
黄小宁 用泡沫塑料和油漆制成的铅球与真正的铅球,两者有不同的内部形状。同样,数学有长度相同但内部形状不同的伪≌直线段。 几何学有史2300年来一直认定附着在直线z上的直线段一定是z的一部分。其实这是2300年肉眼直观错觉——百年病态集论的症结。 …...
汽车网关(GW)技术分析
一、引言 在现代汽车电子系统中,汽车网关(Gateway,简称 GW)扮演着至关重要的角色。随着汽车电子技术的不断发展,汽车内部的电子控制单元(Electronic Control Unit,简称 ECU)数量不断…...

Telnet命令详解:安装、用法及应用场景解析
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「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卷题库疯狂收录中,刷题点这里 专栏导读 本专栏收录于《华为OD机试真题(Python/JS/C/C)》。 刷的越多,抽中的概率越大,私信哪吒,备注华为OD,加入华为OD刷题交流群,…...

打破欧美10年芯片垄断,杨振宁教授关门弟子,仅用三年创造奇迹
有这么一位超级厉害的中国人,硬是把欧美那边垄断了十年的芯片技术给“撬”开了!说起来,这才是我们该追的真正明星啊!那么,这位大神到底是谁?又是怎么让欧美芯片圈儿里的人听到她的名字就心里发怵的呢&#…...
OpenCV视频I/O(20)视频写入类VideoWriter之用于将图像帧写入视频文件函数write()的使用
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 cv::VideoWriter::write() 函数用于将图像帧写入视频文件。 该函数/方法将指定的图像写入视频文件。图像的大小必须与打开视频编写器时指定的大…...
音视频入门基础:FLV专题(14)——FFmpeg源码中,解码Script Tag的实现
一、引言 在《音视频入门基础:FLV专题(9)——Script Tag简介》中对Script Tag进行了简介,本文讲述FFmpeg源码中是怎样解码FLV文件的Script Tag,拿到里面的信息。 二、flv_read_packet函数 从《音视频入门基础&#x…...

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

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

[实用工具]Docker安装nextcloud实现私有云服务和onlyoffice
Nextcloud是一款开源的云存储和协作平台,允许用户在自己的服务器上存储和访问文件,同时提供强大的协作工具。它可以替代商业云存储服务,让用户拥有完全控制和自主管理自己的数据。 Nextcloud支持文件上传和下载,可以通过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多数据源,通过配置动态加载发送者和消费者
前言 最近做项目,需要支持kafka多数据源,实际上我们也可以通过代码固定写死多套kafka集群逻辑,但是如果需要不修改代码扩展呢,因为kafka本身不处理额外逻辑,只是起到削峰,和数据的传递,那么就需…...

【华为】基于华为交换机的VLAN配置与不同VLAN间通信实现
划分VLAN(虚拟局域网)主要作用: 一、提高网络安全性 广播域隔离访问控制增强 二、优化网络性能 减少网络拥塞提高网络可管理性 sysytem-view #进入系统视图配置参数 vlan batch 10 20 #批量创建vlan LSW3: int g0/0/1 port…...

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

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

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

wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...

微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...

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

在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: 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 请求,并检查收到的响应。它以以下模式之一…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑: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 开发工作中,合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式:工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...