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爱好者值得关注
评论
【送书福利】《Java面试八股文:高频面试题与求职攻略一本通》
先来唠唠最近粉丝面试回来跟我聊天,基本上都提到一个点,在面试过程中八股文占比很高(八股文70%、项目20%、10%算法)除了一些搞算法突出的厂除外。其实现在很多厂八股都是逐渐深入的方式来问,所以大家在学习的过程中,针对一些重点的内容,最好深入去学习,不然还是比较难应对这种追问式的问题。最近刚好从一位
Java后端技术
0
“渣女”怎样抵抗收入暴跌,去杭州找大厂程序员“接盘”
一位好友给我分享了一张图片,看过之后,我直呼毁三观。不知是哪位大厂员工蒙在鼓里多年,被“渣女”耍的团团转。这也难怪外面传“要嫁就嫁程序员,钱多话少死得早。”敢情成为了某些“心机女”的接盘侠。我不由得想起了曾经轰动一时的“程序员苏享茂事件”,被前妻翟欣欣索要千万跳楼自杀。我在网上详细查了这个案件资料。
Python涨薪研究所
0
字节面试:如何解决MQ消息积压问题?
面试题大全:www.javacn.siteMQ(Message Queue)消息积压问题指的是在消息队列中累积了大量未处理的消息,导致消息队列中的消息积压严重,超出系统处理能力,影响系统性能和稳定性的现象。1.消息积压是哪个环节的问题?MQ 执行有三大阶段:消息生产阶段。消息存储阶段。消息消费阶段。
Java中文社群
0
【PythonCode】力扣Leetcode16~20题Python版
作者通常周更,为了不错过更新,请点击上方“Python碎片”,“星标”公众号前言力扣Leetcode是一个集学习、刷题、竞赛等功能于一体的编程学习平台,很多计算机相关专业的学生、编程自学者、IT从业者在上面学习和刷题。在Leetcode上刷题,可以选择各种主流的编程语言,如C++、JAVA、Pyth
Python 碎片
0
推理部署工程师面试题库
作者丨进击的Killua来源丨https://zhuanlan.zhihu.com/p/673046520编辑丨GiantPandaCV最近团队在招人,记录一些常用的面试问题,持续更新中。1. 描述一下SM的结构?(INT32/FP32/FP64)CUDA core,Tensor Core,LD/S
GiantPandaCV
32
实战必备-数据清洗、数据存储、数据可视化-《AKShare-初阶-实战应用》
✔️课程介绍本课程主要给大家介绍 AKShare 的实战应用部分,主要包括对 AKShare 获取到的数据进行数据清洗,数据存储和数据可视化。课中会提供我们在进行数据处理中的最佳实践!课程目录✔️获取方式如下: 直接购买订阅: ¥39.8/年🔗扫码进入课程店铺:🔅懒得
数据科学实战
31
41岁,北大毕业,大厂工作15年,职级P9的老公被裁。赔偿818148.61元
41岁,某大厂P9职级的老公被裁。当时消息来的很突然,3月中旬他在微信上告知我的时候,真的很震惊。因为到了他这个级别,应该属于公司中层以上了,竟然没有一点预兆。老公在和+1领导深入交谈后,坦然接受这一切,N+1的赔偿。3月底赔偿金到账了,818148.61元。他感觉是个吉利的数字,也算是一种自我安慰
Python涨薪研究所
0
面试太紧张怎么破?
JavaGuide官方网站:javaguide.cn不知各位在参加第一次技术面试的时候是否会非常紧张?拿我自己来说,当时真是紧张坏了,面试完之后也处于懵懵的状态。这篇文章简单聊聊面试紧张这个话题,分享一些建议帮助有这方面困扰的朋友来减轻这个问题。要正确看待面试紧张怯场这件事情,正常情况下,参加面试大
JavaGuide
0