如何解决leetcode中三数之和的问题
发表于:2024-10-23 作者:千家信息网编辑
千家信息网最后更新 2024年10月23日,这篇文章给大家分享的是有关如何解决leetcode中三数之和的问题的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。题目链接https://leetcode-cn.com/pr
千家信息网最后更新 2024年10月23日如何解决leetcode中三数之和的问题
这篇文章给大家分享的是有关如何解决leetcode中三数之和的问题的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。
题目链接
https://leetcode-cn.com/problems/3sum-closest/
题目描述
给定一个包括 n
个整数的数组 nums
和 一个目标值 target
。找出 nums
中的三个整数,使得它们的和与 target
最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
解题方案
思路
标签:排序和双指针
本题目因为要计算三个数,如果靠暴力枚举的话时间复杂度会到O(n^3),需要降低时间复杂度
首先进行数组排序,时间复杂度O(nlogn)
在数组nums中,进行遍历,每遍历一个值利用其下标i,形成一个固定值nums[i]
再使用前指针指向
start = i + 1
处,后指针指向end = nums.length - 1
处,也就是结尾处根据
sum = nums[i] + nums[start] + nums[end]
的结果,判断sum与目标target的距离,如果更近则更新结果ans同时判断sum与target的大小关系,因为数组有序,如果
sum > target
则end--
,如果sum < target
则start++
,如果sum == target
则说明距离为0直接返回结果整个遍历过程,固定值为n次,双指针为n次,时间复杂度为O(n^2)
总时间复杂度:O(nlogn) + O(n^2) = O(n^2)
代码
class Solution { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int ans = nums[0] + nums[1] + nums[2]; for(int i=0;itarget) end--; else if(sum < target) start++; else return ans; } } return ans; }}
画解
感谢各位的阅读!关于"如何解决leetcode中三数之和的问题"这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!
复杂
复杂度
数组
时间
指针
个数
结果
题目
之和
问题
内容
指向
整数
更多
目标
篇文章
排序
不错
实用
有序
数据库的安全要保护哪些东西
数据库安全各自的含义是什么
生产安全数据库录入
数据库的安全性及管理
数据库安全策略包含哪些
海淀数据库安全审计系统
建立农村房屋安全信息数据库
易用的数据库客户端支持安全管理
连接数据库失败ssl安全错误
数据库的锁怎样保障安全
惠普服务器配远控
中国开放存取数据库有哪些
自身网络技术评价
数据库调出
人工神经网络技术路线图
足球联赛资料数据库
安徽调度服务器品牌云主机
网络安全流量受到监控怎么办
平谷ibm服务器回收公司
大话西游2 第三届服务器联赛
广州社交软件开发费用是多少
上位软件开发和PLC哪个好
永吉软件开发专业
软件开发中团队协调体现在哪
诸城关系网络技术公司
会考信息技术数据库视频
局网络安全工作专题会议记录
眼镜行业软件开发电话
淄博管理软件开发公司
苏州app软件开发团队
青浦区特定软件开发销售公司
服务器管理器取消开机启动
网络安全涉及范围是
最新qq代理服务器
pubg手游服务器连接
我的世界服务器如何做一个副本
软件开发委托协议(个人)
信创服务器价钱
网络安全维护基础
西青区企业网络技术诚信合作