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
|
|||
|
|
//}
|