首页 > 代码库 > leetcode-3Sum Closest-16
leetcode-3Sum Closest-16
输入一组数字,任选三个数字,求这三个数字加起来最接近某一值的和。
枚举三个数字的话ON^3
更高效的方法,利用了求一组数字中两个数字的和的方法,即用两个指针指向首尾往中间移动,前提是数组有序,所以先排序。遍历数组,然后用两个指针指向这个元素后面序列的首尾,如果这三个数字的和到target的距离比之前的ans到target的距离更小,就更新ans,然后移动后面两个指针:如果当前和大于target,后面的指针往前移,如果小于,前面的指针后移。时间ON^2
1 class Solution { 2 public: 3 int threeSumClosest(vector<int>& nums, int target) { 4 if(nums.size()<3) return 0; 5 sort(nums.begin(),nums.end()); 6 int ans=nums[0]+nums[1]+nums[2]; 7 for(int i=0;i<nums.size();i++){ 8 int j=i+1,k=nums.size()-1; 9 while(j<k){10 int sum=nums[j]+nums[k]+nums[i];11 if(sum==target) return target;12 if(sum<target) j++;13 else k--;14 int tmp=abs(sum-target);15 if(tmp<abs(ans-target)) ans=sum;16 } 17 }18 return ans;19 }20 };
leetcode-3Sum Closest-16
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。