3
leetCode 15 和 16 三数之和
source link: https://studygolang.com/articles/35507
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
leetCode 15 和 16 三数之和
双指针写法
先预排序,再遍历
code 15
func threeSum(nums []int) [][]int {
target := 0
res := [][]int{}
L := len(nums)
if L < 3 {
return res
}
sort.Ints(nums)
for index := 0; index < L - 2; index ++ {
if nums[index] > 0 {
break
}
start := index + 1
// 去重
if index > 0 && nums[index] == nums[index - 1] {
continue
}
end := L - 1
for start < end {
if nums[index] + nums[start] + nums[end] < target {
start += 1
// 去重
for nums[start] == nums[start - 1] && start < end {
start += 1
}
} else if nums[index] + nums[start] + nums[end] > target {
end -= 1
// 去重
for nums[end] == nums[end + 1] && start < end {
end -= 1
}
} else {
res = append(res, []int{nums[index], nums[start], nums[end]})
start += 1
end -= 1
// 去重
for nums[start] == nums[start - 1] && nums[end] == nums[end + 1] && start < end {
start += 1
end -= 1
}
}
}
}
return res
}
code 16
func threeSumClosest(nums []int, target int) int {
L := len(nums)
if L == 0 {
return target
}
sort.Ints(nums)
delta := nums[0] + nums[1] + nums[2] - target
for index := 0; index < L - 2; index ++ {
start := index + 1
if index > 0 && nums[index] == nums[index - 1] {
continue
}
end := L - 1
for start < end {
newDelta := nums[index] + nums[start] + nums[end] - target
if newDelta == 0 {
return target
}
if abs(delta) > abs(newDelta) {
delta = newDelta
}
if newDelta < 0 {
start += 1
for nums[start] == nums[start - 1] && start < end {
start += 1
}
} else {
end -= 1
for nums[end] == nums[end + 1] && start < end {
end -= 1
}
}
}
}
return delta + target
}
func abs(num int) int {
if num >= 0 {
return num
} else {
return -1 * num
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK