首页 > 代码库 > 【leetcode】3Sum Closest
【leetcode】3Sum Closest
3Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).与 3Sum类似，只是需要添加一个变量distance，用来记录和target距离最小的a+b+c
1 class Solution { 2 public: 3 int threeSumClosest(vector<int> &num, int target) { 4 5 int n=num.size(); 6 sort(num.begin(),num.end()); 7 8 int i,j,k; 9 int a,b,c;10 int result;11 int distance=INT_MAX;12 13 for(i=0;i<n-2;i++)14 {15 j=i+1;16 k=n-1;17 18 while(j<k)19 {20 a=num[i];21 if(i>0&&num[i]==num[i-1])22 {23 break;24 }25 b=num[j];26 if(j>i+1&&num[j]==num[j-1])27 {28 j++;29 continue;30 }31 32 c=num[k];33 if(k<n-1&&num[k]==num[k+1])34 {35 k--;36 continue;37 }38 39 if(a+b+c==target)40 {41 return target;42 }43 else if(a+b+c<target)44 {45 if(target-(a+b+c)<distance)46 {47 result=a+b+c;48 distance=target-result;49 }50 j++;51 }52 else if(a+b+c>target)53 {54 if((a+b+c)-target<distance)55 {56 result=a+b+c;57 distance=result-target;58 }59 k--;60 }61 }62 }63 64 return result;65 66 67 }68 };
【leetcode】3Sum Closest
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。