难度
中等
题目
给定一个整数类型的数组，其中三个数字之和等于0，以二维数组的形式返回所有符合条件的数字组合并且不可重复。
Example 如下：
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
思路
思路一
运用 hash 表，先确定第一个值，之后再确定第二个值并进行排序，时间复杂度为O(n²)。
代码
方法一
func threeSum(_ nums: [Int]) -> [[Int]] {
// [值 : 出现的次数]
var numDict : [Int:Int] = [:]
// i 是数组里面每项的值
for i in nums {
if numDict[i] == nil {
numDict[i] = 1
} else {
numDict[i] = numDict[i]! + 1
}
}
var results : [[Int]] = []
for (num1, count1) in numDict {
// 将每一项出现次数进行 减一 操作
numDict[num1] = count1 - 1
for (num2, count2) in numDict {
let num3 = 0 - num1 - num2
// 进行排序 去除重复项 并且确定 num2
guard count2 > 0 && num1 <= num2 && num2 <= num3 else {
continue
}
if (num2 == num3 && count2 >= 2) || (num2 != num3 && numDict[num3] != nil) {
results.append([num1, num2, num3])
}
}
// 将每一项出现次数进行 恢复 操作
numDict[num1] = count1
}
return results
}
