问题描述
这是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):