【刷题日记】15. 三数之和

15. 三数之和

两数之和可以用巧思也可以用map

三数之和会更加复杂一点,且这道题还需要考虑避免重复答案!

思路:

  1. 特判:检如果numsnull 或长度小于 3直接返回空数组。
  2. 排序:使用 sort对数组进行升序排序。就变成了(-x,0,x)这样子的顺序。
  3. 遍历数组:遍历数组确定第一个数cur=num【i】。如果当前数和前一个数相同跳过(去重);如果 cur 大于 0,直接 break,因为后面加上任何更大的数和都不会是 0了。
  4. 双指针:初始化两个指针 lr(分别指向cur后续数的最左和最右数)。进入 while 循环(条件是l<r),计算三数之和sum。
  • 如果 sum === 0:找到一个三元组,添加到结果 res 中。然后进行去重,移动左指针 l 和右指针 r,直到遇到不同的值。(这个很重要!!)
  • 如果 sum < 0:左指针 l++增加总和。
  • 如果 sum > 0:右指针 r--减少总和。

代码:

//排序+双指针
var threeSum = function (nums) {
    let res = [];
    let len = nums.length;
    if (nums == null || len < 3) return res;
    nums.sort((a, b) => a - b);//升序排序(-x,0,x从小到大)
    for (let i = 0; i < len; i++) {
        let cur = nums[i];//第一个数(当前数)
        if (nums[i] > 0) break;//和后面的数相加也不会会是0
        if (i > 0 && cur == nums[i - 1]) continue;//去重(注意要判断i>0,因为第一个数没有前一个数)
        let l = i + 1, r = len - 1;//双指针,当前数之后数的前后结点
        while (l < r) {
            const sum = nums[l] + nums[r] + cur;
            if (sum === 0) {
                res.push([cur, nums[l], nums[r]])
                while (l < r && nums[l] == nums[l + 1]) l++;//去重
                while (l < r && nums[r] == nums[r - 1]) r--;//去重
                l++;
                r--;
            } else if (sum < 0) {
                l++;
            } else {
                r--;
            }
        }
    }
    return res;
};

 注意,我这里一开始有想过,直接在找三元组的时候,对num用set去重,这样子是不行的,因为题目所说的:

指的是同一个位置的数不能重复出现在三元组中,只是下标不能相同,但不是值不能相同。

所以需要去重的是最终的组合,而不是值。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/881076.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

JS实现树形结构数据中特定节点及其子节点显示属性设置的技巧(可用于树形节点过滤筛选)

大家好&#xff0c;今天我要分享的是如何在树形结构的数据中&#xff0c;根据特定条件设置节点及其所有子节点的显示属性。在实际项目中&#xff0c;这种需求非常常见&#xff0c;特别是在需要动态展示和隐藏节点的情况下。下面我将通过一个具体的示例来讲解实现过程。 需求分析…

Web开发:ABP框架3——入门级别的接口增删改查实现原理

一、上节回顾 运用了ABP框架&#xff0c;使用了EFcore进行增删改查 二、程序的入口 代码解说&#xff1a; public class Program // 定义程序主类 {public async static Task<int> Main(string[] args) // 主方法&#xff0c;返回状态码{// 配置Serilog日志Log.Logger…

【QT】定时器使用

文章目录 关于 Qt 定时器使用的注意细节总结实例-检查工具使用周期时间是否合理UI设计头文件 remind.h源文件 remind.cpp实现效果 关于 Qt 定时器使用的注意细节总结 一、创建与初始化 使用 QTimer 类来创建定时器。可以在构造函数中指定父对象&#xff0c;确保定时器在正确的…

【C++】STL----list常见用法

&#x1f525;个人主页&#x1f525;&#xff1a;孤寂大仙V &#x1f308;收录专栏&#x1f308;&#xff1a;C从小白到高手 &#x1f339;往期回顾&#x1f339;&#xff1a;[C]vector常见用法 &#x1f516; 流水不争&#xff0c;争的是滔滔不息。 文章目录 一、list的介绍li…

【网络通信基础与实践第二讲】包括互联网概述、互联网发展的三个阶段、互联网的组成、计算机网络的体系结构

一、互联网概述 计算机网络是由若干节点&#xff08;node&#xff09;和连接这些节点的链路&#xff08;link&#xff09;组成。 网络之间还可以通过路由器互联起来&#xff0c;这就构成了一个覆盖范围更大的计算机网络。这样的网络称为互联网。 网络把许多计算机连接在一起…

SpringCloud-04 OpenFeign服务调用与负载均衡

OpenFeign是一个声明式、模板化的HTTP客户端&#xff0c;它简化了在Java应用程序中调用RESTful API的过程。OpenFeign是Netflix开发的一个开源项目&#xff0c;它构建在Feign的基础上&#xff0c;为开发者提供了更加简单、灵活的方式来实现HTTP请求。OpenFeign的特点包括&#…

计算机网络:概述 - 性能指标

目录 一. 速率 二. 带宽 三. 吞吐量 四. 时延 五. 时延带宽积 六. 往返时间RTT 七. 利用率 八. 丢包率 此博客介绍计算机网络中的性能指标&#xff0c;性能指标从不同的角度来度量计算机网络的性能。下面介绍几个常用的性能指标&#xff1a; 一. 速率…

服务器非法关闭后MySQL服务启动失败

在写这篇文章前&#xff0c;我弄好了&#xff0c;写完之后把成功安装的几个MySQL都删除了&#xff0c;只留了最后测试成功的服务“mysql-test” ,然后点击运行&#xff0c;发现又出现上图的错误。心态炸了。 本以为定位到问题了&#xff0c;但是这个错误让我迷茫了。我只能临时…

基于spring的ssm整合

目录 基于spring的ssm整合 Spring 框架 SpringMVC 框架 MyBatis 框架 1.创建项目 2.导入依赖 3.导入sql 4.创建jdbc.propries文件 1&#xff09;mysql8以下 2&#xff09;mysql8以上的 5.创建mybatis-config.xml配置文件 6.创建spring-Config.xml文件 7.创建项目所需包和类 1&a…

.whl文件下载及pip安装

以安装torch_sparse库为例 一、找到自己需要的版本&#xff0c;点击下载。 去GitHub的pyg-team主页中找到pytorch-geometric包。网址如下&#xff1a; pyg-team/pytorch_geometric​github.com/pyg-team/pytorch_geometric 然后点击如图中Additional Libraries位置的here&am…

Android系统dumpsys命令详解

文章目录 1. dumpsys 的工作原理2. 基本使用方法执行 dumpsys限制 dumpsys 的输出 3. 常见的 dumpsys 服务1. Activity Manager (activity)2. Battery Service (battery)3. Window Manager (window)4. Package Manager (package)5. Power Manager (power)6. Media DRM (media.d…

青柠视频云——视频丢包(卡顿、花屏、绿屏)排查

一、问题说明 近期有客户反馈&#xff0c;接入平台的设备经常出来卡顿、花屏、录屏的情况&#xff0c;出现这样的场景很是尴尬。 客户是私有化部署在公网环境&#xff0c;于是我们联系客户&#xff0c;对问题进行追踪排查。 二、场景复现 我们现场情况确认的过程中&#xff0c;…

Web 安全基础教程:从零基础入门到精通

一、Web 安全概述 &#xff08;一&#xff09;Web 安全的定义与重要性 1.定义 Web 安全是指保护 Web 应用程序免受各种网络威胁&#xff0c;确保 Web 服务的保密性、完整性和可用性。在当今数字化时代&#xff0c;Web 应用广泛存在于各个领域&#xff0c;从电子商务到社交媒…

Vue 实现高级穿梭框 Transfer 封装

文章目录 01 基础信息1.1. 技术栈1.2. 组件设计a. 竖版设计稿b. 横版设计稿 02 技术方案&#xff08;1&#xff09;初定义数据&#xff08;2&#xff09;注意事项&#xff08;3&#xff09;逻辑草图 03 代码示例3.1. 组件使用3.2. 组件源码./TransferPlus/index.vue./TransferP…

《史上最简单的 SpringCloud 教程》

Finchley版本 Spring Cloud Finchley; Spring Boot 2.0.3 史上最简单的 SpringCloud 教程 | 第一篇: 服务的注册与发现&#xff08;Eureka&#xff09;(Finchley版本)史上最简单的SpringCloud教程 | 第二篇: 服务消费者&#xff08;restribbon&#xff09;(Finchley版本)史上最…

有没有自带财务管理功能的海外仓系统?

在全球化的商业环境中&#xff0c;海外仓作为连接国际市场的物流枢纽&#xff0c;其重要性日益凸显。然而&#xff0c;随着业务范围的扩展和费用类型的多样化&#xff0c;海外仓在财务管理上面临着诸多挑战。传统的手工计费和对账方式不仅耗时费力&#xff0c;而且容易出错&…

网关登录校验(2)----网关如何将用户信息传递给微服务

1.微服务获取用户信息 现在&#xff0c;网关已经可以完成登录校验并获取登录用户身份信息。但是当网关将请求转发到微服务时&#xff0c;微服务又该如何获取用户身份呢&#xff1f; 由于网关发送请求到微服务依然采用的是Http请求&#xff0c;因此我们可以将用户信息以请求头…

Zabbix 部署----安装Zabbix(业务主机)

目录 1、另外准备一台虚拟机(192.xx.xx.20) 设置主机名 关闭防火墙、selinux 准备zabbix-repo 安装zabbix-agent 配置主服务器地址 启动zabbix-agent&#xff1a;10050 1、另外准备一台虚拟机(192.xx.xx.20) 设置主机名 hostname web1 关闭防火墙、selinux syst…

【HTTP】请求“报头”(Host、Content-Length/Content-Type、User-Agent(简称 UA))

Host 表示服务器主机的地址和端口号 URL 里面不是已经有 Host 了吗&#xff0c;为什么还要写一次&#xff1f; 这里的 Host 和 URL 中的 IP 地址、端口什么的&#xff0c;绝大部分情况下是一样的&#xff0c;少数情况下可能不同当前我们经过某个代理进行转发。过程中&#xf…

『功能项目』QFrameWork道具栏物品生成【64】

我们打开上一篇63QFrameWork框架重构OnGUI的项目&#xff0c; OnGUI优点&#xff1a; 简单易用&#xff1a;OnGUI是基于代码的UI系统&#xff0c;对于简单的调试界面或者小型项目来说&#xff0c;可以快速实现UI需求。即时更新&#xff1a;OnGUI的UI元素是即时更新的&#xff…