Leetcode刷题记录17——三数之和

题源：https://leetcode.cn/problems/3sum/?envType=study-plan-v2&envId=top-100-liked

题目描述：
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

思路一：
使用排序加双指针法：
（1）先对nums数组进行升序排序。
（2）使用一个指针i遍历nums数组，先固定三个数中的第一个数。
（3）使用left和right两个指针分别用于指定三个数中的第二个数和第三个数，left初始化为i+1，right初始化为len(nums)-1。
（4）计算三个指针所指数字的和，如果大于0，说明此时数字大了，由于nums数组是升序排序好的，可以将right指针向左移一位，这样三个指针所指数字的和会变小。
（5）如果小于0，说明此时数字小了，可以将left指针向右移一位，这样三个指针所指数字的和会变大。
（6）如果等于0，说明我们找到了一组合规三元组，将其存储在一个二维数组中。
（7）遍历完成后，需要对二维数组去重，此处可以用python自带的set()函数去重。
（8）去重过程中，可以将所有的数组排序后填入集合，此处要注意列表不能作为哈希键，需要用tuple()方法将列表转换为元组后存入集合。
（9）将处理后的集合转化为二维数组，return即可。
代码如下：

class Solution(object):def threeSum(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""three_list = []result_list = []sorted_set = set()nums.sort()for i in range(len(nums) - 2):left = i + 1right = len(nums) - 1while left != right:if nums[i] + nums[left] + nums[right] > 0:right -= 1elif nums[i] + nums[left] + nums[right] < 0:left += 1else:three_list.append([nums[i], nums[left], nums[right]])breakfor list in three_list:sorted_set.add(tuple(sorted(list)))for threelist in sorted_set:result_list.append(threelist)return result_list

运行结果如下，代码逻辑不够完美：

调试了一下代码，问题很明显出现在这句：

else:three_list.append([nums[i], nums[left], nums[right]])break

这句代码使得i固定时无法遍历所有的合规三元组，找到一组后i就向后移动了，肯定不对，改一下代码：

class Solution(object):def threeSum(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""three_list = []result_list = []sorted_set = set()nums.sort()for i in range(len(nums) - 2):left = i + 1right = len(nums) - 1while left < right:if nums[i] + nums[left] + nums[right] > 0:right -= 1elif nums[i] + nums[left] + nums[right] < 0:left += 1else:three_list.append([nums[i], nums[left], nums[right]])left += 1right -= 1for list in three_list:sorted_set.add(tuple(sorted(list)))for threelist in sorted_set:result_list.append(threelist)return result_list

执行时间如下：