leetcode 最接近目标值的子序列和 golang-木庄网络博客

本文摘自网络，作者，侵删。

1755. 最接近目标值的子序列和

由于量级在40，所以单纯的dfs会出问题，所以需要把数组一分为2。然后对得到的数组排序，然后问题就转变为求 2个数组的加和问题。

数组排序
一个从大到小，一个从小到大。求最接近目标的值即可。

func minAbsDifference(nums []int, goal int) int {
    ans := math.MaxInt32
    n := len(nums)
    m := map[int]bool{}
    dfs(nums[:n/2], 0, m)
    A := make([]int, 0, len(m))
    for k, _ := range m {
        ans = min(ans, abs(k-goal))
        if ans == 0 {
            return 0
        }
        A = append(A, k)
    }
    m = map[int]bool{}
    dfs(nums[n/2:], 0, m)
    B := make([]int, 0, len(m))
    for k, _ := range m {
        ans = min(ans, abs(k-goal))
        if ans == 0 {
            return 0
        }
        B = append(B, k)
    }

    sort.Ints(A)
    sort.Ints(B)
    i, j := 0, len(B)-1
    for i < len(A) && j >= 0 {
        v := A[i] + B[j]
        ans = min(ans, abs(v-goal))
        if ans == 0 {
            return 0
        }
        if v >goal{
            j--
        }else{
            i++
        }
    }

    return ans
}

func dfs(A []int, v int, m map[int]bool) {
    if len(A) == 0 {
        m[v] = true
        return
    }
    dfs(A[1:], v, m)
    dfs(A[1:], v+A[0], m)
}

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

本文来自：简书

感谢作者：lucasgao

查看原文：leetcode 最接近目标值的子序列和 golang