Leetcode打卡 | No.015 三数之和

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%多了，可以吃鸡腿了！打赏在哪里！