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 最长公共前缀