[力扣_18] 四数之和

题目人口:点击进入

相关算法:

  • 暴力枚举——时间复杂度O(n^4),加上去重O(res.len),空间复杂度O(1)
  • 双指针+排序——时间复杂度O(n^3),空间复杂度O(logn)主要用于排序

思路和算法:

这题和前两题:16、15很相似,可采用同样的思路来把问题缩小为2Sum,这题我们需要固定两个定值然后获取左右指针,同样也需要对数组进行升序排序,采用快排。

暴力枚举根本过不了,而且C语言实现然后去重太麻烦了,这儿直接记录缩减搜索空间的双指针做法

双指针+排序

为了避免枚举到重复的四元组,则需要保证每一重循环枚举到的元素不小于上一重枚举到的元素,且在同一重循环中不能多次枚举到相同的元素

为了实现上述要求,可以对数组进行排序,并且在循环过程中遵循以下两点:

  • 每一种循环枚举到的下标必须大于上一重循环枚举到的下标
  • 同一层循环中,如果当前元素与上一个元素相同,则跳过当前元素

使用上述方法,可以避免枚举到重复的四元组,因为数组已经排序好了,因此可以使用双指针的方法去掉一重循环

使用两重循环分别枚举前两个数,然后在两重循环枚举到的数之和使用双指针剩下的两个数,假设两重循环枚举到的前两个数分别位于下标 i 和 j ,其中i<j。初始时,左右指针分别指向下标j+1和下标n-1

每次计算四个数的和,并进行如下操作:

  • 如果和等于target,则将枚举到的四个数加到答案中,然后将左指针右移知道遇到不同的数,将右指针左移知道遇到不同的数
  • 如果和小于target,则将左指针右移一位
  • 如果和大于target,则将右指针左移一位

使用双指针枚举剩下两个数的时间复杂度为O(n),因此总时间复杂度为O(n³),但仍然小于暴力枚举

具体实现时,还可以进行一些剪枝操作:

  • 在确定一个数的时候,如果nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target,说明此时剩下的三个数无论取什么值,四数之和一定大于target,因此退出第一重循环
  • 在确定一个数的时候,如果nums[i]+nums[i+1]+nums[i+2]+nums[i+3]<target,说明此时剩下的三个数无论取什么值,四数之和一定小于target,因此第一重循环直接进入下一轮,枚举nums[i+1]
  • 在确定前两个数之后,如果nums[i]+nums[j]+nums[j+1]+nums[j+2]>target,说明此时剩下的两个数无论取什么值,四数之和一定大于target,因此退出第二重循环
  • 在确定两个数的时候,如果nums[i]+nums[j]+nums[n-2]+nums[n-1]<target,说明此时剩下de三个数无论取什么值,四数之和一定小于target,因此第一重循环直接进入下一轮,枚举nums[i+1]

图示如下:(采用pinku-2大佬的)

img

img

img

img

img

img

img

img

img

代码如下所示:

int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes){
     (*returnSize)=0;
     qsort(nums,numsSize,sizeof(int),cmpfunc);
     int **ReturnNums=(int**)malloc(sizeof(int*)*1001);
     *returnColumnSizes = malloc(sizeof(int) * 1001);
     

        for (int i = 0; i < numsSize - 3; i++) {
        if (i > 0 && nums[i] == nums[i - 1])
            continue;
        if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target)
            break;
        if (nums[i] + nums[numsSize - 3] + nums[numsSize - 2] + nums[numsSize - 1] < target)
            continue;
        for (int j = i + 1; j < numsSize - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1])
                continue;
            if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target)
                break;
            if (nums[i] + nums[j] + nums[numsSize - 2] + nums[numsSize - 1] < target)
                continue;

            int left=j+1;
            int right=numsSize-1;
            while(left<right)
            {
               int ans=nums[i]+nums[j]+nums[left]+nums[right];
               if(ans==target)
               {
                  *(ReturnNums+(*returnSize))=(int*)malloc(sizeof(int)*4);
                  ReturnNums[(*returnSize)][0]=nums[i];
                  ReturnNums[(*returnSize)][1]=nums[j];
                  ReturnNums[(*returnSize)][2]=nums[left];
                  ReturnNums[(*returnSize)][3]=nums[right];
                 (*returnColumnSizes)[(*returnSize)] = 4;  
                  (*returnSize)++;
               while(left<right&&nums[left]==nums[left+1]) left++;
               left++;
               while(left<right&&nums[right]==nums[right-1]) right--;
               right--;
               }
               else if(ans>target)
               {
                 right--;
               }
               else
               {
                 left++;
               }
            }
         }
     }

    return ReturnNums;
}

本文链接:

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