力扣 15. 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
方案一：套用两数之和 的思路，遍历元素数组，然后在剩余元素中找到两个和为 0 - num 的数字。
func threeSum(nums []int) (ans [][]int) {
// 元素排序
sort.Ints(nums)
// 遍历元素
for i, v := range nums {
// 过滤重复元素
if i > 0 && nums[i] == nums[i - 1] {
continue
}
// 执行两数之和，target 为 0 - v
for _, two := range twoSum(nums[i+1:], -v) {
ans = append(ans, append(two, v))
}
}
return
}
func twoSum(nums []int, target int) (ans [][]int) {
i, j := 0, len(nums) - 1
for i < j {
// 过滤重复元素
if i > 0 && nums[i] == nums[i - 1] {
i++
continue
}
// 对比指针指向元素之和
switch sum := nums[i] + nums[j]; {
case sum > target:
j--
case sum < target:
i++
default:
ans = append(ans, []int{nums[i], nums[j]})
j--
i++
}
}
return
}
- 时间复杂度：O(n * n)，因为有个嵌套的循环，即遍历原数组然后执行 twoSum 函数，这个过程恰好构成 O(n * n) 复杂度， 之前此前执行元素排序消耗的 O(nlog) ，由于小于 n * n 而被忽略，所以时间复杂度为 O(n * n)。
- 空间复杂度：O(nlogn)，因为快排造成了 nlogn 的空间复杂度，所以空间复杂度为 O(nlogn)。