[力扣_15] 三数之和

题目入口:点击进入

相关算法:

  • 快排+双指针——时间复杂度O(n²),空间复杂度O(n)

这题改版后用C语言写能是道困难题,所以我不打算写暴力枚举,这儿简单说下思路:三个指针不断枚举出所有值等于0的数,每次得到一个和为零的集合,则将其遍历一遍存放结果的序列,若序列中的元素与该集合中的元素重合,则进入下一次的枚举,若不重合,则将其添加到结果序列中

这种思路的时间复杂度,不考虑扫描结果序列为O(n³),是绝对超时的,我们可以采用第一题的思路用双指针来实现O(n²)的算法

双指针

思路如下:

  • 对给定的数组进行快速排序
  • 遍历排序后的数组,选择一个基数

    • 若基数nums[i]>0则直接返回结果,因为数组已经为排好序的了,所以在其之后不可能有数与其相加能等于0
    • 若当前基数nums[i]与上一个基数nums[i-1]相同,则跳过,因为在上一次已经将该基数的所有解枚举了出来,所以在相同的情况下,避免重复则直接跳过
    • 令左指针L=i+1,右指针R=n-1,当L<R时,新设定一个变量为0-nums[i]进入循环(左右两指针的值相加需要等于该变量,才算一个正确的解)
    • 若L+R=0-nums[i],将其添加到结果序列中,同时L++ R--

      • 进行去重操作,当L<R时若L的值与L-1的值相同,则跳过,直到L指向不同的值为止
      • 当L<R时若R的值与R+1的值相同,则跳过,直到指向与前一个不相同的值为止
    • 若L+R>0-nums[i],则代表结果太大,需要移动R指针,选取小的数值,R--
    • 若L+R<0-nums[i],则代表结果太小,需要移动L指针,选取大的数值L++

还是采用大佬画手大鹏的动画演示,配合上述思路就能很好理解了:

img

img

img

img

img

img

img

img

img

img

img

img

代码如下所示:

int CompareByIncreass(const void *a,const void *b)
{
    return *(int*)a-*(int*)b;
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    
    qsort(nums,numsSize,sizeof(int),CompareByIncreass);
    int **returnArray=(int**)malloc(sizeof(int*)*(numsSize*numsSize));
    *returnColumnSizes=(int*)malloc(sizeof(int)*(numsSize*numsSize));
  //我没办法确定大小,只好用平方了
    *returnSize=0;
    if( numsSize < 3 )
    {
        return NULL;
    }
    for(int i=0;i<numsSize-2;i++)
    {  
        if(nums[i]>0) break;
        
        int left=i+1; int right=numsSize-1;
        
        if(i > 0&&nums[i]==nums[i-1]) continue;//定元素去重
        
        int tager=0-nums[i];
        while(left<right)
        {
           int tempSum=nums[left]+nums[right];
           if(tager==tempSum)
           {
             returnArray[*returnSize]=(int*)malloc(sizeof(int)*3);
             (*returnColumnSizes)[*returnSize]=3; //记录列数,这操作绝了 
             returnArray[(*returnSize)][0]=nums[i];
             returnArray[(*returnSize)][1]=nums[left];
             returnArray[(*returnSize)][2]=nums[right];
             left++;right--;
            (*returnSize)++;

             while(left<right && left-1 >= 0 && nums[left]==nums[left-1]) left++;
             while(left<right && right+1 < numsSize && nums[right]==nums[right+1]) right--;
           }
           else if(tager<tempSum)
           {
               right--;
           }
           else{
               left++;
           }
        }
    }
    return returnArray;
}

本文链接:

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