LeetCode第十五题:三数之和【15/1000 python】

👤作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。
会一些的技术:数据分析、算法、SQL、大数据相关、python
作者专栏每日更新:
LeetCode解锁1000题: 打怪升级之旅

LeetCode解锁1000题: 打怪升级之旅https://blog.csdn.net/cciehl/category_12625714.html
python数据分析可视化:企业实战案例https://blog.csdn.net/cciehl/category_12615648.html
备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

在算法和数据结构的学习中,"三数之和"问题是一个非常经典的问题,它不仅考验着程序员的基础算法能力,还涉及到如何有效地利用数据结构来解决实际问题。接下来,我们将通过一个由浅入深的方式,详细解析这个问题,并给出相应的案例和代码实现。

问题描述

在"三数之和"问题中,给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c,使得 a + b + c = 0?找出所有满足条件且不重复的三元组。

 

简单解法 — 暴力法(不推荐)

一种最直观的方法是使用三重循环遍历所有可能的三元组组合,检查它们的和是否为 0。虽然这种方法简单直观,但其时间复杂度为 O(n^3),在数据量较大时会导致严重的性能问题。

代码实现

def three_sum_brute_force(nums):
    n = len(nums)
    result = []
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                if nums[i] + nums[j] + nums[k] == 0:
                    triplet = sorted([nums[i], nums[j], nums[k]])
                    if triplet not in result:
                        result.append(triplet)
    return result

高效解法 — 双指针法

为了优化算法,我们可以采用双指针法。首先对数组进行排序,然后使用一个固定指针遍历数组,对于每个固定指针的位置,使用两个指针(一个在固定指针之后,一个在数组末尾),通过移动这两个指针来搜索和为0的三元组。

解题步骤

  1. 排序:对数组进行排序。
  2. 遍历:固定一个数 nums[i],然后使用左右指针指向 nums[i] 后面的两端,数字分别为 nums[L] 和 nums[R],计算三个数的和 sum 判断是否满足条件。
  3. 去重:跳过重复的数字。

代码实现

def three_sum(nums):
    nums.sort()
    n, result = len(nums), []
    for i in range(n):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        L, R = i+1, n-1
        while L < R:
            total = nums[i] + nums[L] + nums[R]
            if total < 0:
                L += 1
            elif total > 0:
                R -= 1
            else:
                result.append([nums[i], nums[L], nums[R]])
                while L < R and nums[L] == nums[L+1]:
                    L += 1
                while L < R and nums[R] == nums[R-1]:
                    R -= 1
                L += 1
                R -= 1
    return result

案例分析

假设输入数组为 nums = [-1, 0, 1, 2, -1, -4]

  1. 排序后的数组为 [-4, -1, -1, 0, 1, 2]
  2. 固定第一个数为 -4,在 -12 的范围内寻找两数之和为 4 的组合,不存在,移动固定数。
  3. 固定第二个数为第一个 -1,找到了两数之和为 1 的组合,即 [-1, 0, 1]
  4. 继续遍历,找到第二个组合为 [-1, -1, 2]

双指针法图解

给定一个数组nums = [-4, -1, -1, 0, 1, 2],目标是找出所有唯一的三元组,它们的和为0。

1. 排序

首先,对数组进行排序。

排序后的数组: [-4, -1, -1, 0, 1, 2]

2. 遍历和双指针搜索

对数组进行遍历,每次遍历中,固定一个元素,然后用两个指针在固定元素之后的数组部分进行搜索,一个指针从左向右移动(左指针),另一个从右向左移动(右指针)。

第一轮遍历

  • 固定元素: -4 (索引0)
  • 左指针: 在-1 (索引1)
  • 右指针: 在2 (索引5)
数组: [-4, -1, -1, 0, 1, 2]
固定元素: -4 (索引0)
左指针:    ↑ (索引1)
右指针:                  ↑ (索引5)

检查和调整

  • 第一次和为-4 + (-1) + 2 = -3 < 0,左指针向右移动。
  • 左指针移动到第二个-1处,和为-4 + (-1) + 2 = -3 < 0,左指针继续向右移动。
  • 左指针移动到0处,和为-4 + 0 + 2 = -2 < 0,左指针继续向右移动,直到左指针与右指针相遇,这轮遍历结束。

在这轮遍历中,没有找到和为0的三元组。

第二轮遍历

  • 固定元素变为: -1 (索引1)
  • 左指针: 在-1 (索引2)
  • 右指针: 在2 (索引5)
数组: [-4, -1, -1, 0, 1, 2]
固定元素: -1 (索引1)
左指针:        ↑ (索引2)
右指针:                  ↑ (索引5)

遍历的过程重复上述步骤,对每个固定元素,移动左右指针,并根据三数之和是大于还是小于0来调整指针的位置。

 

关键点

  • 当和小于0时,只移动左指针向右。
  • 当和大于0时,只移动右指针向左。
  • 当找到和为0的三元组时,记录下来,并同时移动左指针和右指针,寻找新的可能组合。

3. 去重

为了避免记录重复的三元组,每次在移动指针时,需要跳过重复的值。

结论

通过以上的解析和示例代码,我们可以看出,相比于暴力法,双指针法大大提高了"三数之和"问题的求解效率。

 

 

 

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

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

相关文章

RabbitMQ 消息重复消费问题

RabbitMQ 消息重复消费问题 解决消息重复消费问题 解决消息重复消费问题 需要在消费端考虑消息的幂等性&#xff1a; 幂等性&#xff1a;对一个接口的多次调用和一次调用得到的结果都是一样的 使用数据库的唯一越苏保证幂等性。

应用程序无法正常启动怎么办,应用程序无法正常启动解决方法

电脑使用过程中会碰到各种问题&#xff0c;比如说&#xff0c;有些时候打开应用可能会失败&#xff0c;与此同时还会出现某些提示。最近有用户就遇到了打开软件就提示“应用程序无法正常启动0xc000007b”&#xff0c;这个问题是很常见的&#xff0c;一般是某部分组件损坏导致的…

LeetCode刷题之105. 从前序与中序遍历序列构造二叉树

文章目录 1.题目描述2. 分析2.1 前序遍历2.1.1 什么是前序遍历&#xff1f;2.1.2 前序遍历有什么特点&#xff1f; 2.2 中序遍历2.2.1 什么是中序遍历2.2.2 中序遍历有什么特点&#xff1f; 2.3 后序遍历2.3.1 什么是后序遍历&#xff1f;2.3.2 特点 2.4 总结 3. 解法 1.题目描…

【算法基础】选择排序与冒泡排序的思想与实现

文章目录 1. 选择排序1.1 思想1.2 实现 2. 冒泡排序2.1 思想2.2 实现 1. 选择排序 1.1 思想 选择排序的思想很简单&#xff0c;如上图所示。在每一次遍历子数组的过程中&#xff0c;选择最小的和子数组的第一位交换。子数组的选择从一开始的整个数组&#xff0c;到后面范围逐渐…

Vue2(十四):路由的使用及注意点、嵌套路由、路由的query和params参数、props配置

一、路由的简介 vue-rooter&#xff1a;是vue的一个插件库&#xff0c;专门用来实现SPA应用 1.对SPA应用的理解 1、单页 Web 应用&#xff08;single page web application&#xff0c;SPA&#xff09;。 2、整个应用只有一个完整的页面 index.html。 3、点击页面中的导航链…

CVE-2023-2928 DedeCMS 文件包含漏洞getshell 漏洞分析

DedeCMS&#xff08;也称为织梦CMS&#xff09;是一款基于PHPMySQL的开源内容管理系统。 在 DedeCMS 5.7.106 及之前的版本中发现一个漏洞。它已被宣布为关键。受此漏洞影响的是未知功能的文件uploads/dede/article_allowurl_edit.php。对参数 allurls 的操作会导致代码注入。…

近期整理的前端面试问题大集合【附带答案版】

目录 1、vue的双向绑定原理是什么&#xff1f;里面的关键点在哪里&#xff1f; 2、实现水平垂直居中的方式&#xff1f; 3、常用伪元素有哪一些&#xff1f; 4、移动端如何适配不同屏幕尺寸&#xff1f; 5、本地存储有哪一些&#xff1f;他们三者有什么区别&#xff1f; …

智慧乡村建设探索:数字乡村引领农村发展新方向

目录 一、智慧乡村建设的内涵与意义 二、数字乡村的发展现状 三、数字乡村引领农村发展的新方向 &#xff08;一&#xff09;推动农业现代化&#xff0c;提升农业生产效率 &#xff08;二&#xff09;培育农村新业态&#xff0c;促进农村产业升级 &#xff08;三&#xf…

陶瓷、高频、普通PCB板材有什么不同?

在电子制造中&#xff0c;印刷电路板&#xff08;PCB&#xff09;板材的选择很重要&#xff0c;将直接决定电路板的性能、成本和适用领域&#xff0c;按照市场上应用最广泛的PCB板材&#xff0c;可分为陶瓷、高频及普通&#xff0c;它们三个有什么不同&#xff1f; 1、材质陶瓷…

COTR 网络(图像匹配)

COTR 网络&#xff08;图像匹配&#xff09; 摘要Abstract1. COTR网络1.1 文献摘要1.2 研究背景1.3 COTR网络架构1.4 创新点1.5 实验1.5.1 数据集1.5.2 具体实施1.5.3 实验数据 1.6 结论 2. COTR模型代码实现总结 摘要 本周学习了图像匹配方向的COTR网络模型&#xff0c;COTR通…

记录一次hss不能防护主机的问题

场景&#xff1a;hss的控制台显示不在防护中&#xff0c;其他云主机并没有这个情况。 故障发生的时间是昨天下午15点半左右&#xff0c;运维同事做了重启网卡的操作。service network restart 排查分析&#xff1a; 于是仔细的查看日志&#xff0c;发现报错如下&#xff1a…

openstack中windows虚拟机时间显示异常问题处理

文章目录 一、问题描述二、元数据信息总结 一、问题描述 openstack创建出windows虚拟机的时候&#xff0c;发现时间和当前时间相差8小时&#xff0c;用起来很难受。 参考&#xff1a;https://www.cnblogs.com/hraa0101/p/11365238.html 二、元数据信息 通过设置镜像的元数据…

边缘计算采集网关如何助力制造企业解决数采问题-天拓四方

一、企业背景 某大型制造企业&#xff0c;位于国内某经济发达的工业园区内&#xff0c;拥有多个生产线和智能化设备&#xff0c;致力于提高生产效率、降低运营成本。随着企业规模的扩大和生产自动化的推进&#xff0c;该企业面临着海量数据处理、实时响应和网络安全等多重挑战…

vmware 中的Ubuntu系统虚拟机忘记root密码强制重置操作

忘记密码情况下&#xff0c;vmware虚拟机重置Ubuntu的root密码 在企业使用的vmware ESXI中重置Ubuntu系统root密码 1-本地电脑安装个人版的vmware workstation&#xff0c;目的&#xff1a;vmware ESXI自带的远程控制台无法输入指定的键盘按键&#xff0c;需要借助外部的远程辅…

spring.rabbitmq.listener.simple.default-requeue-rejected = false 和放入死信队列的区别

目录 一、场景 二、使用 spring.rabbitmq.listener.simple.default-requeue-rejected false 2.1 特点 三、 放入死信队列 四、两种区别 一、场景 当我们使用RabbitMq的时候&#xff0c;我们如果业务中有异常&#xff0c;很有可能造成死循环&#xff0c;因为 在RabbitMQ和…

AI提速 OpenAI 新模型GPT-5今年上线?

这两天&#xff0c;有关OpenAI新模型 GPT-5的消息又多了起来。有知情人士称&#xff0c;OpenAI将在今年年中的某个时候发布GPT-5&#xff0c;很可能是在今年夏天期间。OpenAI CEO 萨姆奥特曼在一次播客采访中透露“GPT-5的智能水平得到提升”。 有趣的是&#xff0c;播客的主理…

Spring Security——08,自定义失败处理

自定义失败处理 一、自定义实现类1.1 实现AccessDeniedHandler1.2 实现AuthenticationEntryPoint 二、配置SpringSecurity三、测试3.1 认证失败3.2 权限不足 一键三连有没有捏~~ 我们还希望在认证失败或者是授权失败的情况下也能和我们的接口一样返回相同结构的json&#xff0c…

AI智慧医疗:探索机器学习在医疗保健中的应用与进展

&#x1f9d1; 作者简介&#xff1a;阿里巴巴嵌入式技术专家&#xff0c;深耕嵌入式人工智能领域&#xff0c;具备多年的嵌入式硬件产品研发管理经验。 &#x1f4d2; 博客介绍&#xff1a;分享嵌入式开发领域的相关知识、经验、思考和感悟,欢迎关注。提供嵌入式方向的学习指导…

MySQL学习笔记------事务

事务 事务是一组操作的集合&#xff0c;他是一个不可分割的单位&#xff0c;事务会把所有的操作作为一个整体一起向系统提交或撤销操作请求&#xff0c;即这些操作要么同时成功&#xff0c;要么同时失败 事务操作 create table account(id int comment ID,name varchar(10) …

Java 面向对象基础篇【接口、抽象类、实现类之间的关系】

目录 接口&#xff08;Interface&#xff09;&#xff1a;抽象类&#xff08;Abstract Class&#xff09;&#xff1a;实现类&#xff08;Concrete Class&#xff09;&#xff1a; 接口、抽象类、实现类之间的关系类&#xff08;Class&#xff09;&#xff1a; 接口、抽象类、类…