leetcode 最接近目标值的子序列和 golang

lucasgao · · 116 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

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

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

  1. 数组排序
  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

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

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