2020-11-07：已知一个正整数数组，两个数相加等于N并且一定存在，如何找到两个数相乘最小的两个数？

福哥答案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

}

　　执行结果如下：

2020-11-07：已知一个正整数数组，两个数相加等于N并且一定存在，如何找到两个数相乘最小的两个数？的相关教程结束。