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

内容介绍

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

• 0 <= a, b, c, d < n
• a、b、c 和 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 类型存储中间结果。
   • 内存管理：动态分配内存时，记得释放。