LeetCode-16. 3Sum Closest

xiaoxiao2021-02-28  123

题目要求,求在一个数组中,三个数相加之和与所给数最接近的那个和,返回的是三个数的和。

思路:先将数组由小到大排序,再先确定其中一个数,另外两个数一个从头(最小)开始遍历,另一个从尾(最大)开始遍历,如果所求的数大于所给数,则尾部的数前移,如果小于所给值,则头部后移,循环此过程,把最接近所给数的值保存下来,单过程结束。第一个数需要循环遍历所有的数,最后返回。

class Solution { public: int threeSumClosest(vector<int> &num, int target) { sort(num.begin(),num.end()); int res=num[0]+num[1]+num[2]; for(int i=0;i<num.size();++i){ int a=i+1; int b=num.size()-1; while(a<b){ if(abs(res-target)>abs(num[i]+num[a]+num[b]-target)) res=num[i]+num[a]+num[b]; if(res==target) return res; else if((num[i]+num[a]+num[b])<target) a++; else b--; } } return res; } };

转载请注明原文地址: https://www.6miu.com/read-63601.html

最新回复(0)