93 lines
1.9 KiB
Go
93 lines
1.9 KiB
Go
package main
|
||
|
||
import (
|
||
"fmt"
|
||
"sort"
|
||
)
|
||
|
||
func main() {
|
||
fmt.Println(threeSum([]int{1, -1, -1, 0}))
|
||
}
|
||
|
||
func threeSum(nums []int) [][]int {
|
||
result := make([][]int, 0)
|
||
sort.Ints(nums)
|
||
|
||
for i := 0; i < len(nums); i++ {
|
||
if i-1 >= 0 {
|
||
if nums[i] == nums[i-1] {
|
||
continue
|
||
}
|
||
}
|
||
left, right := i+1, len(nums)-1
|
||
for left < right {
|
||
num := nums[left] + nums[right]
|
||
if num == -nums[i] {
|
||
value := make([]int, 0)
|
||
value = append(value, nums[left], nums[right], nums[i])
|
||
result = append(result, value)
|
||
left++
|
||
right--
|
||
if left-1 > 0 {
|
||
for nums[left] == nums[left-1] && left < right {
|
||
left++
|
||
}
|
||
}
|
||
if right+1 < len(nums) {
|
||
for nums[right] == nums[right+1] && left < right {
|
||
right--
|
||
}
|
||
}
|
||
|
||
} else if num < -nums[i] {
|
||
left++
|
||
} else if num >= -nums[i] {
|
||
right--
|
||
}
|
||
|
||
}
|
||
}
|
||
|
||
return result
|
||
}
|
||
|
||
//func threeSum(nums []int) [][]int {
|
||
// result := make([][]int, 0)
|
||
// hash := make(map[int][]int)
|
||
// result2 := make(map[[3]int]struct{}, 0)
|
||
// right := len(nums) - 1
|
||
// for i := 0; i < right+1; i++ {
|
||
// hash[nums[i]] = append(hash[nums[i]], i)
|
||
// }
|
||
// fmt.Println(hash)
|
||
// for left := 0; left < len(nums); left++ {
|
||
// for right := left + 1; right < len(nums); right++ {
|
||
// sum := nums[left] + nums[right]
|
||
// z := -sum
|
||
// if value, ok := hash[z]; ok {
|
||
// for _, v := range value {
|
||
// if v == left || v == right {
|
||
// continue
|
||
// } else {
|
||
// num := [3]int{nums[v], nums[left], nums[right]}
|
||
// slice := num[:] // 或直接创建新切片：slice := []int{num[0], num[1], num[2]}
|
||
// sort.Ints(slice)
|
||
// result2[[3]int(slice)] = struct{}{}
|
||
// }
|
||
// }
|
||
// } else {
|
||
// continue
|
||
// }
|
||
// }
|
||
// }
|
||
// fmt.Println("result2", result2)
|
||
// for k, _ := range result2 {
|
||
// value := make([]int, 0)
|
||
// for _, v := range k {
|
||
// value = append(value, v)
|
||
// }
|
||
// result = append(result, value)
|
||
// }
|
||
// return result
|
||
//}
|