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

leetcode热题100.三数之和

Problem: 15. 三数之和

文章目录

  • 题目
  • 解题方法
  • 复杂度
  • Code

题目

给你一个整数数组 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 。

提示:

3 <= nums.length <= 3000
− 1 0 5 -10^5 105 <= nums[i] <= 1 0 5 10^5 105

解题方法

我们先考虑最朴实的解法,我们可以遍历三次数组,计算这三次的和,判断是否为零,再通过集合去重,但是这样的时间复杂度是 o ( n 3 ) o(n^3) o(n3),我们思考一下是否可以进行优化。

我们在上面的算法中计算了很多重复的值,我们可以尝试以下排序整个数组,这样我们第一次遍历结束之后,第二次遍历就不需要考虑第一次遍历的数左边的数了,实现了一次剪枝;对于第三次遍历也是一样的,我们不需要考虑第二次遍历的数左边的数。

我们考虑第二,第三次遍历,发现如果此时 nums[i] + nums[j] + nums[k] < 0, 因为 i<j<k,此时我们希望三数之和变大,所以可以右移j,判断是否等于0;同样如果 nums[i] + nums[j] + nums[k] > 0,我们期望他变小一点,则左移 k,检查是否可以等于0。

如果等于零了,说明我们找到了答案,加入最后的结果中即可

注意:关于结果的去重,对于i,left,right,我们都使用while循环排除重复的值,保证结果的唯一性

复杂度

时间复杂度:

遍历了两次数组,所以是: O ( n 2 ) O(n^2) O(n2)

空间复杂度:

添加空间复杂度, 示例: O ( n ) O(n) O(n)

Code

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:nums = sorted(nums)n = len(nums)ans = []i = 0 while i < n-2:while i<n and i>0 and nums[i] == nums[i-1]:i+=1if i < n-2 and nums[i+1] + nums[i+2] + nums[i]>0:breakif i < n-2 and nums[i] + nums[-1] + nums[-2] <0:i+=1continueleft,right = i+1,n-1while left<right:if nums[left]+nums[right] + nums[i] < 0:left += 1elif  nums[left]+nums[right] + nums[i] > 0:right -= 1else:ans.append([nums[i],nums[left],nums[right]])left+=1while left<right and nums[left]==nums[left-1]:left+=1right-=1while left<right and nums[right]==nums[right+1]:right-=1i+=1return ans

相关文章:

leetcode热题100.三数之和

Problem: 15. 三数之和 文章目录 题目解题方法复杂度Code 题目 给你一个整数数组 nums &#xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k &#xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元…...

GitLab服务器忘记root密码处理方式

GitLab服务器忘记root密码处理方式 文章目录 GitLab服务器忘记root密码处理方式1. Gitlab查看用户id号1. 通过api接口查询2. 在Linux终端里直接通过curl命令查询 2. 进入GitLab数据库中查询并修改root密码 1. Gitlab查看用户id号 1. 通过api接口查询 接口查询地址&#xff1a;…...

js-cookie的使用--token的数据实现持久化

1.下载 npm install js-cookie 2.引入 import Cookies from "js-cookie"; 3.使用 // 写入cookie Cookies.set(name, value) // 读取 Cookies.get(name) // > value Cookies.get(nothing) // > undefined // 读取所有可见的cookie Cookies.get() // 删除某项co…...

【实战】SpringBoot自定义 starter及使用

文章目录 前言技术积累SpringBoot starter简介starter的开发步骤 实战演示自定义starter的使用写在最后 前言 各位大佬在使用springboot或者springcloud的时候都会根据需求引入各种starter&#xff0c;比如gateway、feign、web、test等等的插件。当然&#xff0c;在实际的业务…...

网络爬虫采集工具

在当今数字化的时代&#xff0c;获取海量数据对于企业、学术界和个人都至关重要。网络爬虫成为一种强大的工具&#xff0c;能够从互联网上抓取并提取所需的信息。本文将专心分享关于网络爬虫采集数据的全面指南&#xff0c;深入探讨其原理、应用场景以及使用过程中可能遇到的挑…...

【协议】XMLHttpRequest的梳理和总结

1. 前言 本篇梳理和总结一下XMLHttpRequest。 2. XMLHttpRequest原型对象的属性和方法 属性和方法说明示例new XMLHttpRequest() 功能&#xff1a;创建XHR对象 输入&#xff1a; 输出&#xff1a;XHR实例化对象 <略> XMLHttpRequest.prototype .open(method, url, asyn…...

AI教我学编程之C#类的基本概念(1)

前言 在AI教我学编程之C#类型 中&#xff0c;我们学习了C#类型的的基础知识&#xff0c;而类正是类型的一种. 目录 区分类和类型 什么是类&#xff1f; 对话AI 追问 实操 追踪属性的使用 AI登场 逐步推进 提出疑问 药不能停 终于实现 探索事件的使用 异步/交互操作 耗时操…...

前端js 数据结构:对象 object、数组Array 、Map 的创建、增删改 / 遍历数据

目录 前端js 数据结构&#xff1a;对象、数组、Map 的使用1 对象&#xff08;object&#xff09;1.1 创建对象1.1.1 对象字面量(最常用): {}1.1.2 使用 new 关键字和对象构造函数1.1.3 Object.create() 1.2 修改对象1.2.1 直接赋值&#xff1a;对象的属性名直接赋值1.2.2 点号/…...

ARM_Linux的NFS网络文件系统的搭建

介绍&#xff1a; NFS是network filesystem的简称&#xff0c;可以不同的主机通过网络访问远端的NFS服务器共享出来的文件&#xff0c;这样主机通过网络访问NFS服务器&#xff0c;我们就可以在开发板上通过网络访问主机的文件。 为什么要使用NFS网络文件呐&#xff1f; 1、传…...

vscode配置web开发环境(WampServer)

这里直接去下载了集成的服务器组件wampserver&#xff0c;集成了php&#xff0c;MySQL&#xff0c;Apache 可能会出现安装问题&#xff0c;这里说只有图上这些VC包都安装了才能继续安装&#xff0c;进入报错里提供的链接 在页面内搜索相关信息 github上不去可以去镜像站 下载…...

00-Rust前言

问&#xff1a;为什么要近期想学习Rust? 答&#xff1a; Rust出来也是有一段时间了&#xff0c;从Microsoft吵着要重构他们的C"祖传代码"开始&#xff0c;Rust就披着“高效&#xff0c;安全”的头衔。而自己决定要学习Rust&#xff0c;是因为近期发现&#xff1a;涉…...

3.conda的使用

anaconda安装 ubuntu 安装conda 系统架构 uname -m打开终端&#xff0c;不启动base conda config --set auto_activate_base falseconda命令使用 1.查看conda版本 conda --version2.查看conda配置环境 conda config --show3.设置镜像 #设置清华镜像 conda config --add…...

IPv6自动隧道---6to4中继

6to4中继 普通IPv6网络需要与6to4网络通过IPv4网络互通,这可以通过6to4中继路由器方式实现。所谓6to4中继,就是通过6to4隧道转发的IPv6报文的目的地址不是6to4地址,但转发的下一跳是6to4地址,该下一跳为路由器我们称之为6to4中继。隧道的IPv4目的地址依然从下一跳的6to4地…...

低代码开发:解锁数字化转型新维度

在信息化浪潮中&#xff0c;企业正面临着前所未有的挑战与机遇。一方面&#xff0c;市场环境瞬息万变&#xff0c;业务需求迭代频繁&#xff0c;对快速应用开发提出了更高要求&#xff1b;另一方面&#xff0c;传统软件开发模式受限于高成本、长周期等瓶颈&#xff0c;难以满足…...

写一个定时备份数据库的脚本,且只保留最近3天

下面是一个备份数据库并只保留最近3天备份的脚本示例&#xff0c;该脚本使用Python编写&#xff1a; import os import datetime import shutil # 更多源码前往获取&#xff1a;www.qqmu.com # 数据库备份目录 backup_dir "/path/to/backupdir"# 数据库名称 databa…...

java常见面试题:请详细解释如何在Java EE应用中添加EJB

在Java EE应用中添加EJB&#xff08;Enterprise JavaBeans&#xff09;涉及几个关键步骤。下面是一个详细的解释&#xff1a; 创建EJB项目&#xff1a; 首先&#xff0c;你需要创建一个Java EE项目。这通常通过IDE&#xff08;如Eclipse、IntelliJ IDEA等&#xff09;完成&…...

视频监控需求记录

记录一下最近要做的需求&#xff0c;我个人任务还是稍微比较复杂的 需求&#xff1a;需要实现一个视频实时监控、视频回放、视频设备管理&#xff0c;以上都是与组织架构有关 大概的界面长这个样子 听着需求好像很简单&#xff0c;但是~我们需要在一个界面上显示两个厂商的视…...

Self-RAG:通过自我反思学习检索、生成和批判

论文地址&#xff1a;https://arxiv.org/abs/2310.11511 项目主页&#xff1a;https://selfrag.github.io/ Self-RAG学习检索、生成和批评&#xff0c;以提高 LM 的输出质量和真实性&#xff0c;在六项任务上优于 ChatGPT 和检索增强的 LLama2 Chat。 问题&#xff1a;万能L…...

C++基于多态的职工管理系统(附代码下载)

&#x1f308;个人主页&#xff1a;godspeed_lucip &#x1f525; 系列专栏&#xff1a;C从基础到进阶 本文配套markdown文件、配套完整程序&#xff08;vs项目&#xff0c;可直接运行&#xff09;网盘链接请翻阅至文章最底部获取。 职工管理系统&#x1f30f;1、管理系统需求…...

Java安全 CC链1分析

Java安全之CC链1分析 什么是CC链环境搭建jdk下载idea配置创建项目 前置知识Transformer接口ConstantTransformer类invokerTransformer类ChainedTransformer类 构造CC链1CC链1核心demo1demo1分析 寻找如何触发CC链1核心TransformedMap类AbstractInputCheckedMapDecorator类readO…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...