Leetcode打卡 | No.015 三数之和

写在前边:

欢迎和小詹一起定期刷leetcode,每周一和周五更新一题,每一题都吃透,欢迎一题多解,寻找最优解!这个记录帖哪怕只有一个读者,小詹也会坚持刷下去的!

No.15 三数之和

题目:

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

注意:答案中不可以包含重复的三元组。

示例:(可左右滑动)

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

分析:第一道题是两数之和,现在三数,后边会不会四数,五数?还真有四数哈哈。先看这一题,看题目示例看得出来,自动过滤掉了重复三元组,并且是排好序的格式输出,这里可以先将列表进行sort()方法排序。之后进行处理。

第一想法,是固定两个数,然后找第三个数是否在列表之中,且按照符合题意的形式输出。遍历所有情况可以用两层循环嵌套,之后判断第三个数是否在列表的切片之中。简单说步骤如下:

  1. 列表排序,sort()方法
  2. 两层循环嵌套,按照左到右(小到大的方向)遍历
  3. 判断第三个数(即第i,j,个数之和的相反数)是否在j之后的列表切片nums[j+1:]中

代码如下,应该很好理解!

此方法,切实可行,只不过两层循环嵌套,在列表长度较大时会超时!

于是第二种想法。固定一个数,另外两个数之和为第一个数的相反数。这里主要是利用排序后的列表首位向中间逼近的思路执行。步骤介绍如下:

  1. 列表排序,sort()方法
  2. 一层循环,固定一个数,注意从第二个位置开始要考虑是不是和前一个位置的数值相等,避免做不必要的重复计算,比如代码中举例[-1,-1,0]
  3. 固定一个数后,另外两个数索引为除去第一个数的首尾位置。
  4. 取固定数的相反数为目标值target,如果另外两个数之和大于目标值,尾部索引减一,反之首部索引加一
  5. 不大不小即相等,记录这一个解,并首尾索引分别加减一,寻找其他解

代码如下所示:

这一个方法只有一层循环,计算量小很多,结果也很不错,beat90%多了,可以吃鸡腿了!打赏在哪里!

往期推荐

Python 中的 sys.argv 是个什么鬼?

Leetcode打卡 | No.014 最长公共前缀

原文发布于微信公众号 - 小詹学Python(xiaoxiaozhantongxue)

原文发表时间:2018-07-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏糊一笑

关于一道面试题【字符串 '1 + (5 - 2) * 3',怎么算出结果为10,'eval'除外】

最近徘徊在找工作和继续留任的纠结之中,在朋友的怂恿下去参加了一次面试,最后一道题目是: 写一个函数,输入一个字符串的运算式,返回计算之后的结果。例如这样的: ...

56010
来自专栏SeanCheney的专栏

《利用Python进行数据分析·第2版》第7章 数据清洗和准备7.1 处理缺失数据7.2 数据转换7.3 字符串操作7.4 总结

在数据分析和建模的过程中,相当多的时间要用在数据准备上:加载、清理、转换以及重塑。这些工作会占到分析师时间的80%或更多。有时,存储在文件和数据库中的数据的格式...

5899
来自专栏iOSDevLog

数据结构和算法

数据结构和算法是计算机科学中最重要的概念之一。如果您不熟悉计算机科学或编程,本文将为您提供有关数据结构和算法的概述。这也是Landscape系列的第二集。

1594
来自专栏鸿的学习笔记

两个字符串算法

这部分主要使用了动态规划的技术,就是如果两个最大公共子序列相等的话,必然前面的也相等

502
来自专栏编程

Python内置函数int高级用法

int()函数常用来把其他类型转换为整数,例如: >>>int(3.2) 3 >>>int(1/3) 其实,int是Python内置类型之一,之所以能够当作函数...

2589
来自专栏前端杂谈

前端算法-基本排序算法比较

36613
来自专栏菜鸟前端工程师

JavaScript学习笔记005-运算符

892
来自专栏编舟记

泛型编程

泛型编程是一种编程风格,其中算法以尽可能抽象的方式编写,而不依赖于将在其上执行这些算法的数据形式。

862
来自专栏工科狗和生物喵

【计算机本科补全计划】链式存储线性表的一些相关操作

正文之前 不管怎么说,好歹是吧王道的第二章看完了!线性表算法写的我都快吐了,不过成果也是有的,可以写一些稍微复杂的算法了!感动,希望尽早达到老师的要求,然后去实...

3226
来自专栏程序员叨叨叨

5.3 结构类型

Cg 语言支持结构体(structure),实际上 Cg 中的结构体的声明、使用和 C++ 非常类似(只是类似,不是相同)。一个结构体相当于一种数据类型,可以定...

602

扫码关注云+社区

领取腾讯云代金券