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

【leetcode--三数之和】

这道题记得之前做过,但是想不起来了。。总结一下:

函数的主要步骤和关键点:

  1. 排序:对输入的整数数组nums进行排序。这是非常重要的,因为它允许我们使用双指针技巧来高效地找到满足条件的三元组。
  2. 初始化:定义ans列表来存储所有找到的三元组,并初始化三个指针firstsecondthird
  3. 枚举第一个数:使用first指针遍历整个数组。为了避免重复的三元组(例如[-1, 0, 1][0, -1, 1]),我们需要跳过所有与前一个数相同的数。
  4. 设置目标和双指针:将目标和target设置为-nums[first],然后初始化third指针为数组的最后一个元素的索引。此时,我们需要找到两个数(nums[second]nums[third]),它们的和等于target
  5. 枚举第二个数:使用second指针从first + 1开始遍历数组。同样地,为了避免重复的三元组,我们需要跳过所有与前一个数相同的数。
  6. 双指针技巧:当nums[second] + nums[third] > target时,说明third指向的数太大了,我们需要将third向左移动;否则,我们检查是否找到了一个满足条件的三元组。
  7. 避免重复:当secondthird相遇或nums[second] + nums[third] == target时,我们需要检查是否找到了一个有效的三元组,并将其添加到ans列表中。然后,我们继续移动second指针,但在这之前,我们需要跳过所有与当前nums[second]相同的数,以避免找到重复的三元组。
  8. 返回结果:返回存储了所有满足条件的三元组的ans列表。

改进点:这个算法的时间复杂度是O(n^2),其中n是数组nums的长度。

  1. 设 s = nums[first] + nums[first+1] + nums[first+2],如果 s > 0,由于数组已经排序,后面无论怎么选,选出的三个数的和不会比 s 还小,所以只要 s > 0 就可以直接 break 外层循环了。

  2. 如果 nums[first] + nums[n-2] + nums[n-1] < 0,由于数组已经排序,nums[first] 加上后面任意两个数都是小于 0 的,所以下面的双指针就不需要跑了。但是后面可能有更大的 nums[first],所以还需要继续枚举,continue 外层循环。

class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:nums.sort()ans = []n = len(nums)for i in range(n-2):x = nums[i]if i > 0 and x == nums[i-1]:continueif x + nums[i+1] + nums[i+2] > 0:breakif x + nums[-1] + nums[-2] < 0:continuej = i+1k = n-1while j<k:s = x + nums[j] + nums[k]if s < 0:j += 1elif s > 0:k -= 1else:ans.append([x,nums[j],nums[k]])j += 1while j < k and nums[j] == nums[j-1]:j += 1k -= 1while k > j and nums[k] == nums[k+1]:k -= 1return ans

相关文章:

【leetcode--三数之和】

这道题记得之前做过&#xff0c;但是想不起来了。。总结一下&#xff1a; 函数的主要步骤和关键点&#xff1a; 排序&#xff1a;对输入的整数数组nums进行排序。这是非常重要的&#xff0c;因为它允许我们使用双指针技巧来高效地找到满足条件的三元组。初始化&#xff1a;定…...

解决Java中的ClassCastException问题

解决Java中的ClassCastException问题 大家好&#xff0c;我是免费搭建查券返利机器人省钱赚佣金就用微赚淘客系统3.0的小编&#xff0c;也是冬天不穿秋裤&#xff0c;天冷也要风度的程序猿&#xff01; 在Java编程中&#xff0c;ClassCastException是一个常见的运行时异常&am…...

【TensorFlow深度学习】混合生成模型:结合AR与AE的创新尝试

混合生成模型&#xff1a;结合AR与AE的创新尝试 引言自回归模型与自动编码器的简述混合模型的创新尝试组合AR与AE&#xff1a;MADE混合模型在图学习中的应用 结论与展望 在自我监督学习的广阔天地里&#xff0c;混合生成模型以其独特的魅力&#xff0c;跨越了自回归&#xff08…...

Spring:Spring中分布式事务解决方案

一、前言 在Spring中&#xff0c;分布式事务是指涉及多个数据库或系统的事务处理&#xff0c;其中事务的参与者、支持事务的服务器、资源管理器以及事务管理器位于分布式系统的不同节点上。这样的架构使得两个或多个网络计算机上的数据能够被访问并更新&#xff0c;同时将这些操…...

音视频开发32 FFmpeg 编码- 视频编码 h264 参数相关

1. ffmpeg -h 这个命令总不会忘记&#xff0c;用这个先将ffmpeg所有的help信息都list出来 C:\Users\Administrator>ffmpeg -h ffmpeg version 6.0-full_build-www.gyan.dev Copyright (c) 2000-2023 the FFmpeg developersbuilt with gcc 12.2.0 (Rev10, Built by MSYS2 pro…...

标准版小程序订单中心path审核不通过处理教程

首先看自己小程序是不是已经审核通过并上线状态才在站内信里面提醒的&#xff1f; 如果没有提交过审核&#xff0c;请在提交的时候填写。path地址为&#xff1a;pages/goods/order_list/index 如果是已经上线的小程序&#xff0c;当时没要求填这个&#xff0c;但新的政策要求填…...

移植对话框MFC

VC版 MFC程序对话框资源移植 以下均拷贝自上面&#xff0c;仅用来记录 &#xff08;部分有删除&#xff09; 法1&#xff1a; Eg&#xff1a;将B工程调试好的对话框移植到A工程中 1.资源移植 1.1 在2017打开B工程,在工作区Resource标签页中选中Dialog文件夹下的资源文件,按…...

【开源的字典项目】【macOS】:在macOS上能打开mdd and mdx 的github开源项目

【开源的字典项目】【macOS】 在macOS上能打开mdd and mdx 的github开源项目 Here are some GitHub repositories that provide code for opening and reading mdd and mdx files in macOS: 1. MdxEdit: Repository: https://github.com/mdx-editorDescription: A free and …...

已解决javax.security.auth.login.LoginException:登录失败的正确解决方法,亲测有效!!!

已解决javax.security.auth.login.LoginException&#xff1a;登录失败的正确解决方法&#xff0c;亲测有效&#xff01;&#xff01;&#xff01; 目录 问题分析 出现问题的场景 报错原因 解决思路 解决方法 1. 检查用户名和密码 用户名和密码验证 2. 验证配置文件 …...

2741. 特别的排列 Medium

给你一个下标从 0 开始的整数数组 nums &#xff0c;它包含 n 个 互不相同 的正整数。如果 nums 的一个排列满足以下条件&#xff0c;我们称它是一个特别的排列&#xff1a; 对于 0 < i < n - 1 的下标 i &#xff0c;要么 nums[i] % nums[i1] 0 &#xff0c;要么 nums[…...

读AI新生:破解人机共存密码笔记15辅助博弈

1. 辅助博弈 1.1. assistance game 1.2. 逆强化学习如今已经是构建有效的人工智能系统的重要工具&#xff0c;但它做了一些简化的假设 1.2.1. 机器人一旦通过观察人类学会了奖励函数&#xff0c;它就会采用奖励函数&#xff0c;这样它就可以执行相同的任务 1.2.1.1. 解决这…...

C++ 因项目需求,需要将0~2的32次方这个区间的数字保存到内存当中(内存大小为4G),并且可以实现对任意一个数字的增删。(先叙述设计思路,再写岀代码)

问题&#xff1a; C 因项目需求&#xff0c;需要将0~2的32次方这个区间的数字保存到内存当中(内存大小为4G),并且可以实现对任意一个数字的增删。(先叙述设计思路&#xff0c;再写岀代码) 解答 设计思路代码实现说明 为了在有限的内存&#xff08;4GB&#xff09;中存储和操作 …...

Linux 下的性能监控与分析技巧

在日常的服务器管理和问题诊断过程中&#xff0c;Linux 命令行工具提供了强大的支持。本文通过几个常用的示例&#xff0c;介绍如何快速定位问题、监控服务器性能。 无论你是编程新手还是有一定经验的开发者&#xff0c;理解和掌握这些命令&#xff0c;都将在你的工作中大放异…...

不可复制网站上的文字——2种方法

禁用javascript或Console控制台代码 &#xff08;1&#xff09;F12键——设置——勾选禁用javascript &#xff08;2&#xff09;Console控制台敲如下代码&#xff1a; var allowPaste function(e){ e.stopImmediatePropagation(); return true; }; document.addEventListe…...

Ubuntu 22.04上编译安装c++ spdlog library

Very fast, header-only/compiled, C logging library. 请以root身份或sudo执行。 1. 安装必需的依赖项&#xff1a; sudo apt-get update sudo apt-get install git g cmake 2. 克隆 spdlog 仓库&#xff1a; cd /opt git clone https://github.com/gabime/spdlog.git …...

ESP32代码开发入门

ESP-IDF ESP-ADF开发 开发概要 编译环境及SDK搭建 整个开发流程是:下载ESP-IDF, ESP-ADF(按需下载),并安装, 编写hello world工程,编译并烧录到主板验证 可参照ESP32 esp-idf esp-adf环境安装及.a库创建与编译api大部分可以用glibc的接口 做了封装,时间time(NULL), 创建线程p…...

“势”是“态”的偶然性减少

“态势感知”中的“势”指的是一种趋势或倾向性&#xff0c;而“态”则表示状态或局势。这个术语常用于描述在一段时间内系统或事件显示出来的方向性变化或发展趋势。因此&#xff0c;可以将“态势”理解为系统或事件状态变化的趋势&#xff0c;这种变化通常反映出偶然性减少的…...

人脑计算机技术与Neuroplatform:未来计算的革命性进展

引言 想象一下&#xff0c;你在某个清晨醒来&#xff0c;准备开始一天的工作&#xff0c;而实际上你的大脑正作为一台生物计算机的核心&#xff0c;处理着大量复杂的信息。这并非科幻电影的情节&#xff0c;而是人脑计算机技术即将带来的现实。本文将深入探讨FinalSpark公司的…...

新版周易测算系统源码 去授权完美运行

已经去掉授权可以完美运行 更新了三个模板市面上都是几千几千的卖 更新了三套首页新ui 自己后台切换就行 源码大小&#xff1a;338M 源码下载&#xff1a;https://download.csdn.net/download/m0_66047725/89447857 更多资源下载&#xff1a;关注我....

【PYTHON】力扣刷题笔记 -- 0053. 最大子数组和【中等】

题目描述&#xff1a;给你一个整数数组 array: nums &#xff0c;请你找出一个具有最大和的连续子数组 sub-array&#xff0c;返回其最大和 子数组&#xff08;最少包含一个元素&#xff09;: 是数组中的一个连续部分 示例 1&#xff1a; 输入&#xff1a;nums [-2,1,-3,4,-1…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...