自学内容网 自学内容网

力扣第十八题——四数之和

内容介绍

给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):

  • 0 <= a, b, c, d < n
  • abc 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1:

输入:nums = [1,0,-1,0,-2,2], target = 0
输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2:

输入:nums = [2,2,2,2,2], target = 8
输出:[[2,2,2,2]]

提示:

  • 1 <= nums.length <= 200
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109

完整代码

 int comp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
    int** quadruplets = malloc(sizeof(int*) * 1001);
    *returnSize = 0;
    *returnColumnSizes = malloc(sizeof(int) * 1001);
    if (numsSize < 4) {
        return quadruplets;
    }
    qsort(nums, numsSize, sizeof(int), comp);
    int length = numsSize;
    for (int i = 0; i < length - 3; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
            break;
        }
        if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
            continue;
        }
        for (int j = i + 1; j < length - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }
            if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                break;
            }
            if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
                continue;
            }
            int left = j + 1, right = length - 1;
            while (left < right) {
                long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    int* tmp = malloc(sizeof(int) * 4);
                    tmp[0] = nums[i], tmp[1] = nums[j], tmp[2] = nums[left], tmp[3] = nums[right];
                    (*returnColumnSizes)[(*returnSize)] = 4;
                    quadruplets[(*returnSize)++] = tmp;
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    left++;
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return quadruplets;
}

思路详解

整体思路

  1. 首先对数组进行排序,以便后续可以使用双指针法快速查找。
  2. 使用四重循环遍历数组,但通过一些剪枝操作减少不必要的遍历。
  3. 在最内层循环中使用双指针法查找剩余的两个数,以减少时间复杂度。

代码详解

1. 排序
qsort(nums, numsSize, sizeof(int), comp);

使用快速排序对数组进行排序,便于后续查找。

2. 第一层循环
for (int i = 0; i < length - 3; i++) {

遍历数组,固定第一个数。由于需要四个数,所以循环到 length - 3 即可。

3. 去重
if (i > 0 && nums[i] == nums[i - 1]) {
    continue;
}

如果当前数与前一个数相同,则跳过,以避免重复的四元组。

4. 剪枝
if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
    break;
}
if ((long) nums[i] + nums[length - 3] + nums[length - 2] + nums[length - 1] < target) {
    continue;
}

如果当前数加上最小的三个数大于目标值,则后面的数都不可能组成四元组,直接退出循环。同理,如果当前数加上最大的三个数小于目标值,则当前数不合适,继续下一轮循环。

5. 第二层循环
for (int j = i + 1; j < length - 2; j++) {

固定第二个数,从 i + 1 开始遍历。

6. 去重与剪枝(同上)
if (j > i + 1 && nums[j] == nums[j - 1]) {
    continue;
}
if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
    break;
}
if ((long) nums[i] + nums[j] + nums[length - 2] + nums[length - 1] < target) {
    continue;
}
7. 双指针法
int left = j + 1, right = length - 1;
while (left < right) {
    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
    if (sum == target) {
        // 找到一个四元组,保存结果
    } else if (sum < target) {
        left++;
    } else {
        right--;
    }
}

使用双指针法在剩余部分查找剩余的两个数。如果四数之和等于目标值,则保存结果并移动指针以去重;如果小于目标值,则左指针右移;如果大于目标值,则右指针左移。

8. 保存结果
int* tmp = malloc(sizeof(int) * 4);
tmp[0] = nums[i], tmp[1] = nums[j], tmp[2] = nums[left], tmp[3] = nums[right];
(*returnColumnSizes)[(*returnSize)] = 4;
quadruplets[(*returnSize)++] = tmp;

当找到四元组时,分配内存保存结果,并更新返回数组的大小和列数。

总结

该代码通过排序、剪枝和双指针法,有效地解决了四数之和问题,时间复杂度从暴力解法的 O(n^4) 降低到 O(n^3)。

知识点精炼

  1. 问题描述:给定一个整数数组和一个目标值,找出数组中所有不重复的四元组,使得这四个整数的和等于目标值。

  2. 排序:首先对数组进行排序,这是解决四数之和问题的关键步骤,有助于后续的剪枝和双指针操作。

  3. 剪枝:在遍历过程中,通过判断当前数与最小/最大三个数的和是否超过目标值,来提前终止循环,减少不必要的计算。

  4. 去重:在固定前两个数时,如果当前数与前一个数相同,则跳过,以避免产生重复的四元组。

  5. 双指针法:在固定前两个数后,使用双指针法在剩余部分查找剩余的两个数,降低时间复杂度。

  6. 时间复杂度:排序的时间复杂度为 O(nlogn),四重循环的时间复杂度为 O(n^3),总体时间复杂度为 O(n^3)。

  7. 空间复杂度:主要为存储结果数组的空间,最坏情况下为 O(n^2)。

  8. 注意事项

    • 防止整数溢出:在计算四数之和时,使用 long 类型存储中间结果。
    • 内存管理:动态分配内存时,记得释放。

 


原文地址:https://blog.csdn.net/m0_74932528/article/details/140547123

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!