leetcode_015_三数之和解析
三数之和解析
题目
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
暴力解法1
使用3重循环暴力解法
package main
import (
"fmt"
"sort"
)
// 使用3重for循环
func threeSum(nums []int) [][]int {
sort.Ints(nums)
result := make([][]int, 0)
for i := 0; i < len(nums); i++ {
for j := 0; j < len(nums); j++ {
if i == j {
continue
}
for k := 0; k < len(nums); k++ {
if j == k || i == k {
continue
}
if nums[i]+nums[j]+nums[k] == 0 {
x := []int{nums[i], nums[j], nums[k]}
sort.Ints(x)
result = append(result, x)
}
}
}
}
return removeDuplicates(result)
}
func removeDuplicates(slices [][]int) [][]int {
seen := make(map[string]bool)
var result [][]int
for _, slice := range slices {
// 将子切片转换为字符串作为map的键
key := fmt.Sprint(slice)
if !seen[key] {
seen[key] = true
result = append(result, slice)
}
}
return result
}
func main() {
nums := []int{-1, 0, 1, 2, -1, -4}
res := threeSum(nums)
fmt.Println(res)
}
暴力解法2
使用优化后的3重循环暴力解法
package main
import (
"fmt"
"sort"
)
// 使用3重for循环
func threeSum(nums []int) [][]int {
sort.Ints(nums)
result := make([][]int, 0)
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
for k := j + 1; k < len(nums); k++ {
if nums[i]+nums[j]+nums[k] == 0 {
result = append(result, []int{nums[i], nums[j], nums[k]})
}
}
}
}
return removeDuplicates(result)
}
func removeDuplicates(slices [][]int) [][]int {
seen := make(map[string]bool)
var result [][]int
for _, slice := range slices {
// 将子切片转换为字符串作为map的键
key := fmt.Sprint(slice)
if !seen[key] {
seen[key] = true
result = append(result, slice)
}
}
return result
}
func main() {
nums := []int{-1, 0, 1, 2, -1, -4}
res := threeSum(nums)
fmt.Println(res)
}
排序+双指针算法
-
首先对数组进行排序，排序后固定一个数 nums[i]，再使用左右指针指向 nums[i]后面的两端，数字分别为 nums[L] 和 nums[R]，计算三个数的和 sum 判断是否满足为 0，满足则添加进结果集
-
如果 nums[i]大于 0，则三数之和必然无法等于 0，结束循环
-
如果 nums[i] == nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过
-
当 sum == 0 时，nums[L] == nums[L+1] 则会导致结果重复，应该跳过，L++
-
当 sum == 0 时，nums[R] == nums[R−1] 则会导致结果重复，应该跳过，R−−
-
当 sum < 0 时，L++
-
当 sum > 0 时，R–
双指针的左右指针移动条件。
核心思想：排序、双指针移动、跳过重复元素。
跳过重复元素:对于i,在遍历过程中，如果当前元素与前一个元素相同，则跳过它。
对于L,如果当前元素与后一个元素(L+1)相同，则跳过它。
对于R,如果当前元素与前一个元素(R-1)相同，则跳过它。
func threeSum(nums []int) [][]int {
if len(nums) < 3 {
return nil
}
sort.Ints(nums)
result := make([][]int, 0)
for i := 0; i < len(nums); i++ {
if nums[i] > 0 {
break
}
if i > 0 && nums[i] == nums[i-1] {
continue // i去重
}
L := i + 1
R := len(nums) - 1
for L < R {
sum := nums[i] + nums[L] + nums[R]
if sum == 0 {
result = append(result, []int{nums[i], nums[L], nums[R]})
for L < R && nums[L] == nums[L+1] {
L++ // L去重
}
for L < R && nums[R] == nums[R-1] {
R-- // R去重
}
L++
R--
} else if sum < 0 {
L++
} else if sum > 0 {
R--
}
}
}
return result
}