[力扣_16] 最接近的三数之和

题目入口:点击进入

相关算法:

  • 暴力破解——时间复杂度O(n³),空间复杂度O(1)
  • 双指针+排序——时间复杂度O(NlogN)+O(N)=O(N²)

    • 排序需要O(NlogN)的时间,枚举定值又需要O(N)的时间
    • 空间复杂度O(N),主要排序用到的空间

算法与思路:

这道题就是15题的一个变种,用十五题的方法就可做出来,暴力三重循环C语言不会超时,C语言它站起来了!!

双指针的解法和上一题也是,我们可以知道,相差就是三数之和减去给定的tager,为了统一,我们取它的绝对值,我们需要返回所有可能的结果中最小的一个值,则我们可以用一个指针定着一个数,然后左右两指针不断去枚举。

注意特判:若给定的数组大小只有3位的话,则直接返回他们的和即可。

暴力破解:

注意边界,定值 i 从下标0开始枚举到numSize-3的下标处,第二个指针 j 从i+1的位置开始枚举到numSize-2的地方,第三个指针 K 从j+1的位置开始枚举到 numSize-1的地方,不断更新 nums[i] + nums[j] + nums[k] 与target的最小差距值

如图所示:

img

代码如下:

int threeSumClosest(int* nums, int numsSize, int target){
  if(numsSize<=3) return nums[0]+nums[1]+nums[2];
   
  int Min=INT_MAX;
  int ans=0;
  int res=0;
  for(int i=0;i<numsSize-2;i++)
  {
     if(i>0&&nums[i]==nums[i-1]) continue;//防止重复
     for(int j=i+1;j<numsSize-1;j++)
     {
       for(int k=j+1;k<numsSize;k++)
       {
          int temp=nums[i]+nums[j]+nums[k];
          ans=abs(temp-target);
          if(ans<Min) {
              Min=ans;
              res=temp;
          }
       }
     }
  }
   return res;
}

img对,它能过!!

双指针+排序

题目要求找到与目标值最接近的三元组,这里的最接近即为差值的绝对值最小。

我们首先考虑枚举第一个元素a,对于剩下的两个元素b和c,我们希望它们的和最接近target - a 。

对于b和c,如果它们在原数组中枚举的范围(即包括下标的范围,也包括元素值的范围) 没有任何规律可言,那么我们还是只能使用两重循环来枚举所有的可能情况,因此,我们可以考虑对整个数组进行升序排序,这样一来

  • 假设数组的长度为n,我们先枚举a,它在数组中的下标为i
  • 为了防止重复枚举,我们在位置[i+1,n)的范围内枚举b和c

排序的作用在于控制搜索空间,因为我们已经知道数组的有序的,即两个指针分别指向i+1和n-1的位置来缩减搜索空间

如若三数之和要大于给定的目标值,我们则将右指针左移,寻找小的值来判定他们的差距则right--

如若三数之和要小于给定的目标值,我们则右移左指针,寻找大的值来判断他们的差距,则left++、

在每一次得到三个数的时候,我们都用它们之和与给定的target的差距来更新最小值,在这个过程中,如果Min更新, 我们还需要记录下此时的三数之和(因为需要返回的是三数之和)

借用官方题解来证明此算法的正确性,对于三数之和大于target的情况,有如下分析:

如果a+b+c>target,并且我们知道left到right这个范围内数组是按照升序排序的,那么如果right不变而left向右移动,a+b+c的值就会不断增加,显然就不会成为最接近target的值了,因此,我们还可以得知,在left不变的情况下,只有取更小的值与两数相加,才能让它们的差距有可能缩减

则我们将right左移,取得更小的值去测试

同样的,在a+b+c小于target的情况下:

如果a+b+c<target,并且我们知道left到right这个范围内的所有数是按照升序排序的,那么如果left不变而right向左移动,a+b+c的值就会不断减小,显然也不会成为最接近target的值,因此,我们可以让right不变,left向左去寻找更大的数去与两数相加,来寻求更小的差距值

在此过程中,我们可以做个优化,如果a+b+c的和刚好等于target的话,我们则直接返回target,因为此时差距为0,不会有更小的差距。

实际上,left和right就表示了我们当前可以选择的数的范围,而每一次枚举过程中,我们尝试边界上的两个元素,根据它们与target的值的关系,选择“抛弃”左边界元素还是右边界元素,从而减少枚举的范围,这种思路与第11题中的双指针解法也是类似的。

动图演示如下(采用画手大鹏的动图题解)

img

img

img

img

img

img

img

img

img

img

代码如下所示:

int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}
int threeSumClosest(int* nums, int numsSize, int target){
       
     if(numsSize<=3)
         return nums[0]+nums[1]+nums[2];//特殊情况

     int Min=INT_MAX;//赋予最大值,初始化最小值
     int res=0;//返回
     qsort(nums,numsSize,sizeof(int),cmpfunc);//排序

     for(int i=0;i<numsSize-2;i++)//枚举定值
     {
         if(i<0&&nums[i]==nums[i-1]) continue;//避免重复
         int left=i+1;//左指针
         int right=numsSize-1;//右指针
         while(left<right)
         {
             int temp=nums[i]+nums[left]+nums[right];//计算三数之和
             int ans=abs(temp-target);//计算差距

             if(ans<Min){
               Min=ans;
               res=temp;
             }//更新最小值
             
             if(temp>target)//根据情况缩小搜索空间
                 right--;
             else if(temp<target)
                 left++;
             else
                 return temp;//如果相等则直接返回
         
         }
     }
     return res;
//-4 -1 1 2
}

本文链接:

https://nullcode.fun/62.html
1 + 7 =
快来做第一个评论的人吧~