【LeetCode】最接近的三数之和【排序，固定k1,二分寻找k2和k3】

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum-closest

分析：

先给数组排序，O（N*log N）

假定满足要求的三个数：k1<=k2<=k3

先固定k1，然后通过二分寻找k2和k3

循环固定k1，O(N)

二分寻找k2和k3，O(N*log N)

时间主要花费在排序上，总的时间复杂度为O(N*log N)

class Solution {

public:

   int threeSumClosest(vector<int>& a, int t)

{

   int n=a.size();

   int ans;

   int minx=INT_MAX;

   sort(a.begin(),a.end());

   for(int k=0;k<n-2;k++)

   {

       int l=k+1;

       int h=n-1;

       while(l<h)

       {

           int sum=a[k]+a[l]+a[h];

           //cout<<"k="<<k<<" l="<<l<<" h="<<h<<" sum="<<sum<<endl;

           if(abs(sum-t)<minx)

           {

               minx=abs(sum-t);

               ans=sum;

           }

           if(sum>t)

           {

               h--;

           }else if(sum<t)

           {

               l++;

           }else if(sum==t)

           {

               return sum;

           }

       }

   }

   return ans;

}

};

巴特西

【LeetCode】最接近的三数之和【排序，固定k1,二分寻找k2和k3】

最新文章

热门文章