Leetcode 15 3Sum

发表于 |

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

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

题意分析：
在数组找三个数，使三个数的和为0，关键在于答案中不能包含重复三元组！

思路分析：
碰到3Sum问题，我们一般倾向于把他变成一个2Sum问题。
我们首先将数组排序，然后固定住第一个数，在剩下的数组中使用双指针法来寻找剩下两个数。

那如何去重呢？
对于我们固定的第一个数来说，例如[-1, -1, 0, 1, 2]
第一个-1能组成的三元组，完全包含住了第二个-1可能组成的三元组。所以可以将第二个-1跳过。

对于双指针法找到的两个数j,k，一旦成功找到一组(j,k)那么和(j,k)相等的数全部可以跳过。

优化：
因为数组排序后是从小到大的，如果第一个数就大于0了，那已经不可能存在和为0的情况了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 584ms, beats 86.61%
class Solution(object):
    def threeSum(self, nums):
        res = []
        nums.sort()
        for i in range(len(nums)-2):
            if nums[i] > 0: break
            if i > 0 and nums[i] == nums[i-1]: continue
            j,k = i+1,len(nums)-1
            while j < k:
                while j < k and nums[i]+nums[j]+nums[k] < 0:
                    j += 1
                while j < k and nums[i]+nums[j]+nums[k] > 0:
                    k -= 1
                if j == k: break
                if nums[i]+nums[j]+nums[k] == 0:
                    res.append([nums[i],nums[j],nums[k]])
                    while j < k and nums[j] == nums[j+1]:
                        j += 1
                    while j < k and nums[k] == nums[k-1]:
                        k -= 1
                    j += 1; k -= 1
        return res