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

福大大架构师每日一题 · · 340 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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

执行结果如下:


image.png

有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

340 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传