016. 最接近的三数之和 | Leetcode题解
16lz
2021-01-22
点击上方“蓝色字体”，选择“设为星标”
每天复习一道面试题，轻松拿大厂Offer~
题目描述:
给定一个包括 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
难度：
- 难度：中等
- 支持语言：JavaScript、Python、Java
相关标签
- 排序
- 双指针
- 数组
相关企业
- 阿里
- 腾讯
思路：
- 标签：排序和双指针
- 本题目因为要计算三个数，如果靠暴力枚举的话时间复杂度会到 O(n3)O(n^3)O(n3)，需要降低时间复杂度
- 首先进行数组排序，时间复杂度 O(nlogn)O(nlogn)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(n2)O(n^2)O(n2)
- 总时间复杂度：O(nlogn)+O(n2)=O(n2)O(nlogn) + O(n^2) = O(n^2)O(nlogn)+O(n2)=O(n2)
思路2：
和NO.15基本一样的方式，相差在于：
- 不需要去重。
- 不需要完全相等，而是比较当前
sum和target的绝对值的差。
复杂度分析
时间复杂度：O(N2)O(N^2)O(N2)，其中 NNN 是数组 nums\textit{nums}nums 的长度。我们首先需要 O(NlogN)O(N \log N)O(NlogN) 的时间对数组进行排序，随后在枚举的过程中，使用一重循环 O(N)O(N)O(N) 枚举 aaa，双指针 O(N)O(N)O(N) 枚举 bbb 和 ccc，故一共是 O(N2)O(N^2)O(N2)。
空间复杂度：O(logN)O(\log N)O(logN)。排序需要使用 O(logN)O(\log N)O(logN) 的空间。然而我们修改了输入的数组 nums\textit{nums}nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了 nums\textit{nums}nums 的副本并进行排序，此时空间复杂度为 O(N)O(N)O(N)。
代码
JavaScript 实现
/**
* @来源：Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍：一个致力于帮助开发者用代码改变世界为使命的平台，每天都可以在这里找到技术世界的头条内容
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function(nums, target) {
nums.sort((a,b)=>a-b)
let result=null
let min=Infinity
for(let fix=0;fix<nums.length-2;fix++){
let left=fix+1,right=nums.length-1
let sum
while(left<right){
sum=nums[fix]+nums[left]+nums[right]
if(Math.abs(sum-target)<min){
min=Math.abs(sum-target)
if(min===0)return target
result=sum
}
if(sum>target)right--
else left++
}
}
return result
};
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function(nums, target) {
nums.sort((a,b)=>a-b);
let res=nums[0]+nums[1]+nums[2];
let len=nums.length;
for(let i=0;i<len;i++){
let left=i+1,right=len-1;
while(left<right){
let sum=nums[i]+nums[left]+nums[right];
//比较谁距离target更接近采用减法比较差值
if(Math.abs(sum-target)<Math.abs(res-target)){
res=sum;
}
if(sum<target){
left++;
}else if(sum>target){
right--;
}else {
return res;
}
}
}
return res;
};
Java 实现
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int ans = nums[0] + nums[1] + nums[2];
for(int i=0;i<nums.length;i++) {
int start = i+1, end = nums.length - 1;
while(start < end) {
int sum = nums[start] + nums[end] + nums[i];
if(Math.abs(target - sum) < Math.abs(target - ans))
ans = sum;
if(sum > target)
end--;
else if(sum < target)
start++;
else
return ans;
}
}
return ans;
}
}
// 作者：guanpengchn
// 链接：https://leetcode-cn.com/problems/3sum-closest/solution/hua-jie-suan-fa-16-zui-jie-jin-de-san-shu-zhi-he-b/
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
int best = 10000000;
// 枚举 a
for (int i = 0; i < n; ++i) {
// 保证和上一次枚举的元素不相等
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 使用双指针枚举 b 和 c
int j = i + 1, k = n - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
// 如果和为 target 直接返回答案
if (sum == target) {
return target;
}
// 根据差值的绝对值来更新答案
if (Math.abs(sum - target) < Math.abs(best - target)) {
best = sum;
}
if (sum > target) {
// 如果和大于 target，移动 c 对应的指针
int k0 = k - 1;
// 移动到下一个不相等的元素
while (j < k0 && nums[k0] == nums[k]) {
--k0;
}
k = k0;
} else {
// 如果和小于 target，移动 b 对应的指针
int j0 = j + 1;
// 移动到下一个不相等的元素
while (j0 < k && nums[j0] == nums[j]) {
++j0;
}
j = j0;
}
}
}
return best;
}
}
// 作者：LeetCode-Solution
// 链接：https://leetcode-cn.com/problems/3sum-closest/solution/zui-jie-jin-de-san-shu-zhi-he-by-leetcode-solution/
Python 实现
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
n=len(nums)
if n==3: #只有三个数直接相加
return nums[0]+nums[1]+nums[2]
d=float('inf')
nums=sorted(nums)
ans=0
for i in range(n):
l,r=i+1,n-1
while l<r:
x=(nums[i]+nums[l]+nums[r])-target
if abs(x)<d:#更新最短距离
d=abs(x)
ans=nums[i]+nums[l]+nums[r]
if x>0: #大于target，所以需要更小的数，右指针左移
r-=1
elif x<0:#小于target，所以需要更大的数，左指针右移
l+=1
else:#与target相等，直接返回就行
return target
return ans
# 作者：lzh-wu
#链接：https://leetcode-cn.com/problems/3sum-closest/solution/lei-si-shang-yi-ti-de-shuang-zhi-zhen-dai-ma-jian-/
其他
- 原题leetcode链接：https://leetcode-cn.com/problems/3sum-closest/
- 合作方：JavaScript中文网 – 全球极客挚爱的技术成长平台
- 说明：leetcode 题解 | 每日一题
更多相关文章
- PHP如何区分继承链中的$ this指针？
- 堆栈/帧指针作为外部变量
- 自己实现的C++智能指针的功能代码和测试用例
- Android中findViewById()h获取EditText 空指针问题
- java--this指针在哪里存着呢？
- 填充java fx表时出现空指针异常
- Fragment中出现java.lang.NullPointerException 空指针 上下文为
- 二维数组空指针异常
随机推荐