Go 刷 leetcode|大厂面试必备变形题
Go语言精选
共 394字,需浏览 1分钟
· 2020-07-31
今天为大家讲解 LeetCode 第 16 题,顺藤摸瓜,接着昨天的三数之和 leetcode|面试常客双指针算法题
今天为大家分享这道变形题:最接近的三数之和。类似的题目一起讲有利于学习巩固,一起奥利给!
题目描述
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例:
输入:nums = [-1,2,1,-4], target = 1 输出:2 解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示:
3 <= nums.length <= 10^3 -10^3 <= nums[i] <= 10^3 -10^4 <= target <= 10^4
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/3sum-closest 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
了解昨天三数之和的话,这道题应该也会有思路,同样适用双指针解法。
此题的算法思路如下:
对数组进行排序(排序是必须的,否则无法判断及指针移动)。 初始化返回结果 ans 为 nums[0] + nums[1] + nums[2](初始化为Int的最大值也行,反正都是用于判断跟新) 遍历排序后数组,并计算当前指向三数的 sum = nums[i] + nums[l] + nums[r] : 若 abs(target-sum) < abs(target-ans) (abs 是求绝对值),表示当前 sum 距离更近,则更新结果 ans = sum 若 sum < target ,左指针 L 右移 若 sum > target,右指针 R 左移
代码实现
//go
func threeSumClosest(nums []int, target int) int {
sort.Ints(nums) // 排序
length := len(nums)
ans := nums[0] + nums[1] + nums[2]
for i := 0; i < length; i++ {
l, r := i+1, length-1
for l < r {
sum := nums[i] + nums[l] + nums[r]
if AbsInt(target-sum) < AbsInt(target-ans) {
ans = sum
}
if sum < target {
l++
} else if sum > target {
r--
} else {
return ans
}
}
}
return ans
}
func AbsInt(x int) int {
if x < 0 {
return -x
}
return x
}
//java
class Solution {
public int threeSumClosest(int[] nums, int target) {
// 排序
Arrays.sort(nums);
int closestNum = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.length - 2; i++) {
int l = i + 1, r = nums.length - 1;
while (l < r){
int threeSum = nums[l] + nums[r] + nums[i];
if (Math.abs(threeSum - target) < Math.abs(closestNum - target)) {
closestNum = threeSum;
}
if (threeSum > target) {
r--;
} else if (threeSum < target) {
l++;
} else {
// 如果已经等于target的话, 肯定是最接近的
return target;
}
}
}
return closestNum;
}
}
郑重声明:
所展示代码已通过 LeetCode 运行通过,请放心食用~
推荐阅读
站长 polarisxu
自己的原创文章
不限于 Go 技术
职场和创业经验
Go语言中文网
每天为你
分享 Go 知识
Go爱好者值得关注
评论
Go Heap Profile 怎么了?
Go heap profile 是常常用来检查内存泄露和内存占用大问题的问题的手段,而且非常常用。而且,我们也经常创建两个间隔较长的 heap profile, 获取它们的差值来方便查看内存泄露: Hi, 使用多年的 go pprof 检查内存泄漏的方法居然是错的?! [1]今天,度厂的一位同学提出
GoCN
0
好未来测开一面,挺简单!(0428面试原题解析)
大家好,我是二哥呀。今天继续给大家分享春招面试题《好未来测开一面原题》,附详细答案,我会用通俗易懂+手绘图的方式,让天下所有的面渣都能逆袭 😁二哥的 Java 面试指南内容较长,建议正在冲刺 24 届春招和 25 届暑期实习、秋招的同学先收藏起来,面试的时候大概率会碰到,1、二哥的 Linux 速查
沉默王二
0
大厂都在用的 Git 代码管理规范 !
👉 欢迎加入小哈的星球 ,你将获得: 专属的项目实战 / Java 学习路线 / 一对一提问 / 学习打卡 / 赠书福利全栈前后端分离博客项目 2.0 版本完结啦, 演示链接:http://116.62.199.48/ ,新项目正在酝酿中
小哈学Java
2
Go 1.22 的新增功能系列之二:reflect.TypeFor
Go 1.22 的第一个候选版本已经发布,这意味着最终版本即将发布,现在是我在博客中介绍我在这个周期中所做工作的时候了。像往常一样,我的贡献很小,但它们是我的,所以我将从幕后的角度来谈谈它们。首先是reflect.TypeFor。这是整个函数:// TypeFor returns the [Type
GoCN
0
Go早期是如何在Google内部发展起来的
2007年Go诞生于Google,2009年Google正式对外宣布了Go语言的开源!时至今日,距离Go开源已经过去了近15个年头了[1]!Go在Google公司内部究竟是怎样的一个状态呢?前Google员工Yves Junqueira近期撰文从其个人所见所闻谈了Go在Google的历程[2]!这里
GoCN
0
Go 1.22 的新增功能系列之一:cmp.Or
截至撰写本文时,Go 1.22 已经发布几个月了。早就该结束我为 1.22 所做的工作的系列了。抱歉耽搁了这么久,我最近忙于生活事务。如果您错过了我关于reflect.TypeFor(https://blog.carlana.net/post/2024/golang-reflect-type-for
GoCN
1
【送书福利】《Java面试八股文:高频面试题与求职攻略一本通》
先来唠唠最近粉丝面试回来跟我聊天,基本上都提到一个点,在面试过程中八股文占比很高(八股文70%、项目20%、10%算法)除了一些搞算法突出的厂除外。其实现在很多厂八股都是逐渐深入的方式来问,所以大家在学习的过程中,针对一些重点的内容,最好深入去学习,不然还是比较难应对这种追问式的问题。最近刚好从一位
Java后端技术
0
“渣女”怎样抵抗收入暴跌,去杭州找大厂程序员“接盘”
一位好友给我分享了一张图片,看过之后,我直呼毁三观。不知是哪位大厂员工蒙在鼓里多年,被“渣女”耍的团团转。这也难怪外面传“要嫁就嫁程序员,钱多话少死得早。”敢情成为了某些“心机女”的接盘侠。我不由得想起了曾经轰动一时的“程序员苏享茂事件”,被前妻翟欣欣索要千万跳楼自杀。我在网上详细查了这个案件资料。
Python涨薪研究所
0