第十六题(16)LeetCode
题目:给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数,使它们的和与 target 最接近。返回这三个数的和。
假定每组输入只存在恰好一个解。
题目解析:给定数组num,目标t,若存在数组中的三个数满足a+b+c最接近t,返回最接近的那个数(有且仅有1个)。
难度:中等
相关:数组,两个指针
方法:类似三数之和的双指针方法,先对数组进行排序,定义初始最大差值为d,遍历数组,i=0:l-3,如果num[i]=num[i-1],continue;避免重复。问题变成了,在已排序数组中,从i+1,到l-1寻找两个数使得和最接近k=-num[i]。left指向i+1,right指向l-1,计算得到当前的和与k的差值,并与d作比较,更新d,如果d=0,直接返回。如果left+right<-nums[i],left右移,否则right左移。class Solution { public: int threeSumClosest(vector& nums, int target) { sort(nums.begin(),nums.end()); int mint=INT_MAX; int tt; for(int i=0;i0&&nums[i]==nums[i-1]) continue; int t=target-nums[i]; int a1=i+1; int a2=nums.size()-1; int sum; sum=nums[a1]+nums[a2]; while(a1
时间复杂度:O(n2)
空间复杂度:O(logn)