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):

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