当前位置:网站首页>November 07, 2020: given an array of positive integers, the sum of two numbers equals N and must exist. How to find the two numbers with the smallest multiplication?

November 07, 2020: given an array of positive integers, the sum of two numbers equals N and must exist. How to find the two numbers with the smallest multiplication?

2020-11-07 23:08:33 Fuda Dajia architect's daily question

Fogo's answer 2020-11-07:

1. Hashifa . 2. Sort + Double pointer pinch .

golang The code is as follows :

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), " Hashifa ")
    fmt.Println(twoSumMultiplication2(nums, 12), " Sort + Double pointer pinch ")
}

// Hashifa 
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]     // Difference value  =  The target - Element value 
        if _, ok := map0[complement]; ok { // If there is a difference in the dictionary , It means that we have found 
            // Make sure complement It's the smaller value 
            if complement > nums[i] {
                complement, nums[i] = nums[i], complement
            }

            // Who is small and who keeps it 
            if complement < min {
                min = complement
                // If the minimum is 1, You don't have to cycle .
                if min == 1 {
                    break
                }
            }

        } else {
            // If there is no difference in the dictionary , Cache the current value of the array 
            map0[nums[i]] = struct{}{}
        }
    }

    return min
}

// Sort + Double pointer pinch 
func twoSumMultiplication2(nums []int, target int) int {
    // Sort 
    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
}

The results are as follows :  Insert picture description here

版权声明
本文为[Fuda Dajia architect's daily question]所创,转载请带上原文链接,感谢