77 lines
1.4 KiB
Go
77 lines
1.4 KiB
Go
package top100liked
|
|
|
|
import (
|
|
"fmt"
|
|
"sort"
|
|
"testing"
|
|
)
|
|
|
|
// https://leetcode.cn/problems/3sum/?envType=study-plan-v2&envId=top-100-liked
|
|
|
|
func threeSum(nums []int) [][]int {
|
|
sort.Ints(nums)
|
|
|
|
n := len(nums)
|
|
res := make([][]int, 0)
|
|
|
|
for i := 0; i < n-2; i++ {
|
|
// 去重第一个数
|
|
if i > 0 && nums[i] == nums[i-1] {
|
|
continue
|
|
}
|
|
|
|
// 剪枝：当前最小三数和已经大于 0
|
|
if nums[i]+nums[i+1]+nums[i+2] > 0 {
|
|
break
|
|
}
|
|
|
|
// 剪枝：当前最大三数和仍然小于 0
|
|
if nums[i]+nums[n-2]+nums[n-1] < 0 {
|
|
continue
|
|
}
|
|
|
|
target := -nums[i]
|
|
l, r := i+1, n-1
|
|
|
|
for l < r {
|
|
sum := nums[l] + nums[r]
|
|
|
|
if sum == target {
|
|
res = append(res, []int{nums[i], nums[l], nums[r]})
|
|
|
|
leftVal := nums[l]
|
|
rightVal := nums[r]
|
|
|
|
// 命中后，左右都跳过重复值
|
|
for l < r && nums[l] == leftVal {
|
|
l++
|
|
}
|
|
for l < r && nums[r] == rightVal {
|
|
r--
|
|
}
|
|
} else if sum < target {
|
|
leftVal := nums[l]
|
|
|
|
// 当前 l 太小，且重复的 l 也一样太小，直接跳过
|
|
for l < r && nums[l] == leftVal {
|
|
l++
|
|
}
|
|
} else {
|
|
rightVal := nums[r]
|
|
|
|
// 当前 r 太大，且重复的 r 也一样太大，直接跳过
|
|
for l < r && nums[r] == rightVal {
|
|
r--
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
return res
|
|
}
|
|
|
|
func TestS6(t *testing.T) {
|
|
nums := []int{-100, -70, -60, 110, 120, 130, 160}
|
|
fmt.Printf("%+v", threeSum(nums))
|
|
}
|