专栏首页皮皮瞎学编程Array - 16. 3Sum Closest

Array - 16. 3Sum Closest

16. 3Sum Closest

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

思路:

给定一个数组,找出三个数的和最接近target,和15题很像,做法类似,都是对于每一位元素,用双指针找出另外两个数,更新出一个最小的结果就可以。

代码:

go:

func threeSumClosest(nums []int, target int) int {

    if nums == nil || len(nums) <= 2 {
        return math.MinInt32
    }
    
    res := nums[0] + nums[1] + nums[len(nums) - 1]
    sort.Ints(nums)
    for i := 0; i < len(nums) - 2; i++ {
        start := i + 1
        end := len(nums) - 1
        for start < end {
            sum := nums[i] + nums[start] + nums[end]
            if sum > target {
                end--
            } else {
                start++
            }
            if abs(sum - target) < abs(res - target) {
                res = sum
            }
        }
    }
    
    return res
    
}

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Array - 283. Move Zeroes

    Given an array nums, write a function to move all 0's to the end of it while mai...

    用户5705150
  • Backtracking - 47. Permutations II

    Given a collection of numbers that might contain duplicates, return all possible...

    用户5705150
  • Array - 228. Summary Ranges

    Given a sorted integer array without duplicates, return the summary of its range...

    用户5705150
  • LeetCode 259. 较小的三数之和(固定一点,内层双指针)

    给定一个长度为 n 的整数数组和一个目标值 target,寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组...

    Michael阿明
  • LeetCode 18. 四数之和(双指针)

    给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d...

    Michael阿明
  • 程序员面试金典 - 面试题 16.24. 数对和(双指针/哈希map)

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/pairs-with-sum-lcci 著作权归领扣...

    Michael阿明
  • 剑指Offer - 面试题57. 和为s的两个数字(双指针)

    输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。

    Michael阿明
  • LeetCode 1403. 非递增顺序的最小子序列(排序)

    给你一个数组 nums,请你从中抽取一个子序列,满足该子序列的元素之和 严格 大于未包含在该子序列中的各元素之和。

    Michael阿明
  • leetcode 题解~两数之和 ~ C++做法

    伪君子
  • 一文带你把这几个经典求和问题按的死死的!

    今天为大家带来三道求和问题,通过文字,图画,动图为大家解析,很容易就能读懂,每道题目都是经典题,大家快来打卡吧。

    公众号袁厨的算法小屋

扫码关注云+社区

领取腾讯云代金券