[Leetcode] 15. 3Sum

PRoblem:

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] ]

思路 1. 暴力枚举法+分类讨论法。这种题直接暴力枚举的话，时间复杂度高达O(n^3)，所以我一开始对暴力枚举加上了分类讨论。三个数之和为0有以下几种情况：

因此，首先对输入的数组进行“正数，零，负数”分类，然后再穷举这四种情况的所有组合。最后发现，时间复杂度仍然接近O(n^3)，这优化意义不大。

#Note: 以下两种方法是题目“2sum”的延伸。“2sum”求的是：对于输入的数组，求出两数之和等于某特定值的所有组合。在这题目“3sum”中，因为题目是求a,b,c使得a+b+c=0，所以我们可以看作是求a,b使得a+b=-c。这样其实就是穷举版的“2sum”问题。 2. 借助hash表。对输入的数组放入一个哈希表中，然后遍历哈希表的每一个数a，然后调用2sum函数：新建一个用于标记的集合set，遍历输入数组的每一个值b（此时要去掉一个数a，因为数具有不可复用性），判断集合set中是否存在一个数c，使得c = -a-b。如果有，则为目标答案，加到result list中；如果没有，则把b数加入到集合set中。 这样做的好处在于减少了一层循环，使得时间复杂度降为O(n^2)，但同时空间复杂度是O(n)。另外，调用2sum函数时，也可以遍历已建立好的hash表，可以更节省时间。不过需要注意的是要考虑[0，0，0]这种情况。 3. 双向游标法。首先将输入数组nums排序，然后遍历输入数组的每个数a作为target值，然后调用2sum函数：对于有序数组（除去数a），定义两个指针指向首尾两端，即，一个指向nums[0],一个指向num[len(nums)]。然后有如下三种情况： (1) 若当前和小于-a，则左指针右移； (2) 若当前和大于-a，则右指针左移； (3) 若当前和等于-a，则为目标答案。 这里排序的时间复杂度为O(nlogn)，遍历的时间复杂度为O(n^2)，所以总的时间复杂度近似于O(n^2).

Solution :

方法2

方法3

ref: 1. CSDN bolg 2. leetcode discussion