美文网首页
最接近的三数之和

最接近的三数之和

作者: scriptllh | 来源:发表于2019-02-22 16:21 被阅读0次

leetcode 16

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

三数之和的变形

func threeSumClosest(nums []int, target int) int {
    sort.Ints(nums)
    bestTarget := nums[0] + nums[1] + nums[2] // initial value
    if len(nums) == 3 {
        return bestTarget
    }
    for i := 0; i < len(nums)-2; i++ {
        newTarget := target - nums[i]
        l, r := i+1, len(nums)-1
        for l < r {
            if abs(bestTarget-target) > abs(nums[l]+nums[r]+nums[i]-target) {
                bestTarget = nums[l] + nums[r] + nums[i]
            }
            if bestTarget == target {
                return bestTarget
            }
            if nums[l]+nums[r] < newTarget {
                l++
            } else {
                r--
            }
        }
    }
    return bestTarget
}

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

相关文章

  • algrithrom

    求和问题,双指针解决 done 两数之和 三数之和 最接近三数之和 四数之和 链表反转问题 done 链表反转 链...

  • LeetCode-16 最接近的三数之和

    题目:16. 最接近的三数之和 难度:中等 分类:数组 解决方案:双指针 今天我们学习第16题最接近的三数之和,这...

  • 双指针总结

    左右指针 主要解决数组中的问题:如二分查找 盛最多水的容器 三数之和 四数之和 最接近三数之和 快慢指针 主要解决...

  • LeetCode练习day1-数组相关

    LeetCode16 最接近的三数之和 相似题目:LeetCode15 三数之和 题目详情 给你一个长度为 n 的...

  • 最接近的三数之和

    题目来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/3sum...

  • 最接近的三数之和

    题目 思路 题解

  • 最接近的三数之和

    题目地址 1.思路 第一步很容易想到的就是降维处理,三个数相当于三维,那么我确定一个数的时候只剩下2维,这样就把问...

  • 最接近的三数之和

    leetcode 16 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中...

  • 最接近的三数之和

    来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/3sum-c...

  • 双指针法(算法)

    案例: 盛最多水的容器、三数之和、最接近的三数之和 双指针法一般对应于有序数组的情况,通过调节指针(左右移动),...

网友评论

      本文标题:最接近的三数之和

      本文链接:https://www.haomeiwen.com/subject/kgveyqtx.html