题目链接

详情请见链接： https://leetcode.cn/problems/3sum/description/

思路

假设三个有序的数分别为$a,b,c$，可以用：

  • 排序：首先对输入的数组排序，方便后面遍历

  • 双指针： 针对$a$做第一层遍历。因为要求$a+b+c==0$，且数组已经有序，所以必然会满足$a \leq b \leq c$。接下来：

    • left指针指向$b$，在$a$的下一个数据开始，从左往右遍历。

    • right指针指向$c$，在数组末端开始，从右往左遍历。

    当满足三数之和等于0，而且各自的索引不一样，且这个组合不曾出现（需要避免重复），则可以作为新的一个结果，并移动两个指针。但当：

    • $a+b+c>0$时，我们需要将整体的值变小，如今只有$c$能够变小，因此需要调小$c$，right指针左移，再做判断。

    • $a+b+c<0$时，同理需要将整体的值变大，如今在第一层遍历中$a$是不可变的，只有$b$能够变大，因此需要调大$b$，即left指针往右移。

两层遍历都完成之后，最后返回结果。

第一次尝试

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        result = list()
        for i, a in enumerate(nums):
            # two pointers
            left = i + 1
            right = len(nums) - 1
            while left < right:
                if a + nums[left] + nums[right] == 0:
                    _res = sorted([a, nums[left], nums[right]])
                    # check duplication
                    if _res not in result:
                        result.append(_res)
                    # update pointers
                    left += 1
                    right -= 1
                elif a + nums[left] + nums[right] > 0:
                    # nums[right] is larger
                    right -= 1
                else:
                    # nums[left] is smaller
                    left += 1
        return result

结果

7467ms, 仅超越5%的提交。

第二次尝试

分析上回

数组中的每个数据可能是重复的，因此需要考虑当前指针指向的值，和下一个值有可能相等的情况。但是第一次尝试的做法，每找到一个满足条件的组合，都要去结果列表里面遍历，查看当前组合是否已经存在，这样造成了额外的时间开销。因此，在每一层遍历时，无论是$a$，还是$b,c$，都可以考虑跳过相同的值，继续往前移，这样也能保证得出来的结果是不重复的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        result = list()
        for i, a in enumerate(nums):
            # check and remove duplication on a
            if i > 0 and a == nums[i-1]:
                continue
            # two pointers
            left = i + 1
            right = len(nums) - 1
            while left < right:
                if a + nums[left] + nums[right] == 0:
                    result.append([a, nums[left], nums[right]])
                    # check and remove duplication on b and c
                    while left < right and nums[left] == nums[left+1]:
                        left += 1
                    while left < right and nums[right] == nums[right-1]:
                        right -= 1
                    # update pointers
                    left += 1
                    right -= 1
                elif a + nums[left] + nums[right] > 0:
                    # nums[right] is larger
                    right -= 1
                else:
                    # nums[left] is smaller
                    left += 1
        return result

结果

834ms，超越32.19%的提交，有大幅度的提升。

第三次提交

分析上回

尽管有了较大幅度的提升，但是连一半的提交都没超越，说明还有较大的改进空间。其实从数学上看，会不会还会有一些能够推理出来的结论能应用上的？于是反观原来的条件：a+b+c==0。因为数组是有序的，其实在做遍历的时候，我们可以发现：假如当$a$已经大于0时，这个条件是永远都不会成立的，这时已经可以直接返回结果了，因为再做下去已经无意义了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        result = list()
        for i, a in enumerate(nums):
            # bound condition
            if a > 0:
                return result
            # check and remove duplication on a
            if i > 0 and a == nums[i-1]:
                continue
            # two pointers
            left = i + 1
            right = len(nums) - 1
            while left < right:
                if a + nums[left] + nums[right] == 0:
                    result.append([a, nums[left], nums[right]])
                    # check and remove duplication on b and c
                    while left < right and nums[left] == nums[left+1]:
                        left += 1
                    while left < right and nums[right] == nums[right-1]:
                        right -= 1
                    # update pointers
                    left += 1
                    right -= 1
                elif a + nums[left] + nums[right] > 0:
                    # nums[right] is larger
                    right -= 1
                else:
                    # nums[left] is smaller
                    left += 1
        return result

结果

627ms，超越了72.72%提交。

总结

三数之和问题主要可以应用排序+双指针解决，最好尽可能考虑边界条件，以便提前过滤掉。这题解法比较正常。早前面试的时候问了一下，心里想着刚好刷到过，兴奋了一下就暴露了自己的想法，结果面试官就换题。不过还好面试官已经是我的同事了。所以咱面试的时候还是得低调一些。

时间复杂度

排序：$O(N \log N)$

遍历数组：$O(n)$

双指针遍历: $O(n)$

总体： $O(N \log N) + O(n) * O(n) = O(n^2)$