3Sum

问题描述

这是LeetCode上的一道题：
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
 [-1, 0, 1],
 [-1, -1, 2]
]

问题分析

这道题要求我们求出一个数组中的和为0的三个数，简单的看，我们首先可以想到最简单的方法：穷举。将任意三个数搭配尝试，最后根据要求去掉重复的情况就行了（个人觉得这步并不是很容易实现）。
-1 + 0 + 1  Yes
-1 + 0 + 2  No
-1 + 0 + -1  No
-1 + 0 + -4  No
-1 + 1 + 2  No
-1 + 1 + -1  No
-1 + 1 + -4  No
…
0 + 1 + 2  No
…
2 + -1 + -4  No
时间复杂度是O(n^3)，简单粗暴却不是最优的，我们可以思考一下怎么去优化我们的算法。
首先，我们看看我们使用穷举法有哪些可以使用的信息没有用到。 第一步 -1 + 0 + 1=0 后，我们是否还要考虑-1 + 0 + 2 和 -1 + 0 + -1 等等呢，显然是不需要的，题目要求不允许重复，那么-1,0固定后，第三个数找出一个以后就不用在继续再找了。我们再看 -1 + 1 + -1 这一步，计算出 -1 + 1 + -1 后还有必要计算 -1 + 1 + -4吗，也是不用的，因为-1 + 1 + -1 比 0 小，-1换成-4，只会更小。从上面两个分析我们可以看出 三个数之和s与0的关系蕴含着一些信息，我们可以利用它来减少查找的次数，我们得到下面这条信息：
已知固定了a，b，选择c，a+b+c=s，则有如下：
如果 s = 0：a,b,c即为一个解，改变a，b继续寻找
如果 s > 0：c 应该取更小的数
如果 s < 0: c 应该取更大的数
如何找更小更大的数呢，可以使用排序，排序与后面的查找是并列关系且排序的时间复杂度可以低至O(nlogn)，所以我们可以放心地先对数组排一次序，排完序后发现相同的数会连在一起，这样我们可以使用一些技巧完成题目的不许重复的要求。同时我们可以固定a，b修改为固定a，移动b和c。

实现

下面是python的一个实现代码（已AC）：

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

                 
        return results