题意
一个数组,找到三个数,使其相加等于0,找出这些组合
思路
解法一: 暴力查找,三层循环寻找三个数,检查组合,时间复杂度
O(n3)
解法二: 理论上,只要找到两个数,那么第三个数也就确定是几了,只需要找到两个数,然后查找满足条件的第三个数是否存在就行了,如果存在,那么满足条件,进行组合,时间复杂度
O(n2)
解法三:
如果三个数相加为0,那么必定有三种情况
一个正数或者至少一个负数一个负数或者至少一个正数三者皆为0
第三种情况暂且不考虑,因为在进行检查前两种情况的过程中即可验证第三种情况,首先对序列进行排序,然后下标
i
从0到
length−3
,因为组合要三个数,下标k从
length−1
开始,下标
j
从i 1到
k−1
,然后下标
i
不变,j和
k
,进行变化,三者所对应序列中的数之和sum:
sum==0
满足条件,可加入组合,但是同种组合应视为同一组合,所以说
j
和
k应去寻找下一个不相同的位置的数
sum>0
说明
k
代表的数太大,所以说
k减小
sum<0
说明
j
代表的数太小,所以说
j增大
优化:因为实现对序列进行了排序,所以说可以确定下标
i
为三个数中最小的那一个,如果i对应的数>0,那么后面两个数必定也是大于0的,所以说,当
i
对应的数>0时,直接停止寻找.时间复杂度O(n2)
结果
Your runtime beats 46.15 % of swift submissions
代码
class Solution {
func threeSum(_ nums: [Int]) ->
[[Int]] {
let len = nums.count
var ans =
[[Int]]()
if len <
3 {
return ans
}
var tempNums = nums
tempNums.sort()
for i
in 0..<len -
2 {
if i !=
0 && tempNums[i] == tempNums[i -
1]{
continue
}
if tempNums[i] >
0 {
break
}
var j = i +
1
var k = len -
1
while j < k {
let sum = tempNums[i] + tempNums[j] + tempNums[k]
if sum ==
0 {
let ansNums = [tempNums[i], tempNums[j], tempNums[k]]
ans.append(ansNums)
while j +
1 < k && tempNums[j] == tempNums[j +
1] {
j +=
1
}
j +=
1
while k -
1 > j && tempNums[k] == tempNums[k -
1] {
k -=
1
}
k -=
1
}
else if sum <
0 {
j +=
1
}
else {
k -=
1
}
}
}
return ans
}
}