采用跟 3Sum相同的思想来解决,复杂度是o(n2);
int threeSumClosest(vector<int>& num,int tar) { int n=num.size(); sort(num.begin(),num.end()); int i,l,r; int res=10000000; bool smaller=false,found=false; for(i=0;i<n;i++) { l=i+1,r=n-1; while(l<r) { int t=num[i]+num[l]+num[r]; if (t<tar) { if(tar-t<res) { res=tar-t; smaller=true; } l++; } else if(t>tar) { if (t-tar<res) { res=t-tar; smaller=false; } r--; } else { res=0; smaller=false; found=true; break; } } if (found) break; } return smaller?tar-res:tar+res; }
因为题目保证了有满足条件的数,所以可以直接return,否则要判断found;