福哥答案2020-11-07:
1.哈希法。
2.排序+双指针夹逼。
golang代码如下:
package main
import (
"fmt"
"sort"
)
const INT_MAX = int(^uint(0) >> 1)
func main() {
nums := []int{2, 1, 3, 4, 5, 6, 9, 8, 7}
fmt.Println(twoSumMultiplication1(nums, 12), "哈希法")
fmt.Println(twoSumMultiplication2(nums, 12), "排序+双指针夹逼")
}
//哈希法
func twoSumMultiplication1(nums []int, target int) int {
map0 := make(map[int]struct{})
min := INT_MAX
for i := 0; i < len(nums); i++ {
complement := target - nums[i] //差值 = 目标值-元素值
if _, ok := map0[complement]; ok { //如果字典里有差值,说明已经找到了
//确保complement是较小的那个值
if complement > nums[i] {
complement, nums[i] = nums[i], complement
}
//谁小保存谁
if complement < min {
min = complement
//如果最小值是1,就不用循环了。
if min == 1 {
break
}
}
} else {
//如果字典里没有差值,缓存数组的当前值
map0[nums[i]] = struct{}{}
}
}
return min
}
//排序+双指针夹逼
func twoSumMultiplication2(nums []int, target int) int {
//排序
sort.Slice(nums, func(i, j int) bool {
return nums[i] < nums[j]
})
sumtemp := 0
min := INT_MAX
for i, j := 0, len(nums)-1; i < j; {
sumtemp = nums[i] + nums[j]
if target == sumtemp {
if min > nums[i] {
min = nums[i]
if min == 1 {
break
}
}
i++
} else if target > sumtemp {
i++
} else {
j--
}
}
return min
}
执行结果如下:
有疑问加站长微信联系(非本文作者)