LeetCode: 16. 3Sum Closest

引言

题目链接:https://leetcode.com/problems/3sum-closest/description/

题目大意

给出一个包含n个整数的数组nums和一个目标数字target,在数组中找到三个整数使得它们的总和最接近目标target,输出这个最接近目标值的数字

  • Example

题解

这题其实是第15题的变种,相信看了这篇题解举一反三很容易能拿下这题,LeetCode:15.3Sum题解,Click Here!

第15题是找到所有三个数的和等于0的组合,这题是找到三个数的和接近目标值,其实除了返回的结果不同整个过程都是类似的,只需要在15题的判断条件上进行修改即可,判断条件修改如下

由于数组有序,根据当前选取三个数字的和和目标值比较,大于目标值,第三个数字从剩余数组从后往前选取,小于目标值,第二个数字从剩余数组从前往后选取,每次选定三个目标后将选取数字的和和目标值差值比较,更新更小差值的数组和即可

复杂度

时间复杂度 O(n^2)

空间复杂度 O(1)

AC代码

c++版本

go版本

历史上的今天:

繁夜

发表评论


:[微笑]::[撇嘴]::[色]::[发呆]::[得意]::[流泪]::[害羞]::[闭嘴]::[睡]::[大哭]::[尴尬]::[发怒]::[调皮]::[呲牙]::[惊讶]::[难过]::[酷]::[冷汗]::[抓狂]::[吐]::[偷笑]::[可爱]::[白眼]::[傲慢]::[饥饿]::[困]::[惊恐]::[流汗]::[憨笑]::[大兵]::[奋斗]::[咒骂]::[疑问]::[嘘...]::[晕]::[折磨]::[衰]::[骷髅]::[敲打]::[再见]::[擦汗]::[抠鼻]::[鼓掌]::[糗大了]::[坏笑]::[左哼哼]::[右哼哼]::[哈欠]::[鄙视]::[委屈]::[快哭了]::[阴险]::[亲亲]::[吓]::[可怜]::[笑哭]::[doge]::[泪奔]::[无奈]::[托腮]::[斜眼笑]::[喷血]::[惊喜]::[骚扰]::[小纠结]::[我最美]::[羊驼]::[幽灵]::[吃]::[OK]::[爱你]::[抱拳]::[勾引]::[强]::[弱]::[拳头]::[爱心]::[喝彩]::[西瓜]::[啤酒]::[玫瑰]::[凋谢]::[礼物]::[拥抱]::[月亮]::[菊花]::[棒棒糖]::[蛋]::[刀]::[菜刀]::[炸弹]::[手枪]:

刷新评论