LeetCode15 三数之和

给你一个整数数组 nums ，判断是否存在三元组 $[\text{nums}[i],\text{nums}[j],textnums[k]]$ 满足 $i!=j、i!=k$ 且 $j!=k$ ，同时还满足 $\text{nums}[i]+\text{ nums}[j]+\text{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.第一种方法那就是暴力解法，直接三个循环遍历得到结果，但时间复杂度为O(n3)O(n^3)O(n3)。
2.第二种方法就是双指针方法。首先需要做的是对数组进行升序排序，时间复杂度为$O(n\log n)$；然后固定好三元组第一个元素的位置，左指针初始化指向除第一个元素外的数组的第一个位置，右指针指向末尾位置。如果nums >target， 右指针左移可以让nums变小；同理如果nums<target，左指针右移；当左右指针遍历完后，移动我们第一个元素的位置。
3.另外，由于不能输出重复的三元组，所以需要去重操作。

Code

class Solution(object):def threeSum(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""res = []nums.sort()for i in range(len(nums)):l = i + 1r = len(nums) - 1if i > 0 and nums[i] == nums[i-1]:continuewhile l < r:if nums[i] + nums[l] + nums[r] > 0:r -= 1elif nums[i] + nums[l] + nums[r] < 0:l += 1else:subres = [nums[i], nums[l], nums[r]]res.append(subres)while l < r and nums[l] == nums[l+1]:l += 1while l < r and nums[r] == nums[r-1]:r -= 1l += 1r -= 1return res