C语言算法-解答四数之和问题的C语言实现

题目

给定一个包含 n 个整数的数组 nums 和一个目标值 target，找出 nums 中所有满足四个元素之和等于目标值的唯一四元组。答案中不可以包含重复的四元组。

引言

四数之和问题是一个与三数之和问题相似的问题，在处理数组中的元素组合时，我们需要考虑去重和优化搜索过程。解决这个问题需要使用双指针和排序等技巧。

算法思路

我们将使用双指针的方法来解决四数之和问题。

算法的步骤如下：

1. 对数组 nums 进行排序。
2. 初始化一个结果集 result，用于存储满足条件的四元组。

3. 遍历排序后的数组 nums，对于每个元素 nums[i]：

   • 如果 nums[i] 大于目标值的四分之一，表示后续的元素都会大于目标值，无法满足和为目标值的条件，直接返回结果。
   • 如果 nums[i] 与前一个元素相等，为了避免重复的结果，跳过当前循环。
   • 使用双指针 j 和 k，分别指向 i 的下一个位置和数组末尾。

   • 在 j 和 k 之间进行双指针遍历，判断四个数的和与目标值的关系：

     • 如果四个数的和等于目标值，将它们添加到结果集中。
     • 如果四个数的和大于目标值，将 k 向左移动一位。
     • 如果四个数的和小于目标值，将 j 向右移动一位。
   • 在 j 和 k 移动过程中，需要注意跳过重复的元素。
4. 返回结果集 result。

代码实现

下面是使用C语言实现的代码：

#include <stdio.h>
#include <stdlib.h>

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

int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
    qsort(nums, numsSize, sizeof(int), cmp);

    int capacity = 16;
    int** result = (int**)malloc(sizeof(int*) * capacity);
    *returnColumnSizes = (int*)malloc(sizeof(int) * capacity);
    *returnSize = 0;

    for (int i = 0; i < numsSize - 3; i++) {
        if (nums[i] > target / 4) {
            break;
        }

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

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

            int left = j + 1;
            int right = numsSize - 1;

            while (left < right) {
                int sum = nums[i] + nums[j] + nums[left] + nums[right];

                if (sum == target) {
                    result[*returnSize] = (int*)malloc(sizeof(int) * 4);
                    result[*returnSize][0] = nums[i];
                    result[*returnSize][1] = nums[j];
                    result[*returnSize][2] = nums[left];
                    result[*returnSize][3] = nums[right];
                    (*returnColumnSizes)[*returnSize] = 4;
                    (*returnSize)++;

                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }

                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }

                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }

    return result;
}

int main() {
    int nums[] = {1, 0, -1, 0, -2, 2};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int target = 0;

    int returnSize;
    int* returnColumnSizes;
    int** result = fourSum(nums, numsSize, target, &returnSize, &returnColumnSizes);

    printf("Result:\n");
    for (int i = 0; i < returnSize; i++) {
        printf("[%d, %d, %d, %d]\n", result[i][0], result[i][1], result[i][2], result[i][3]);
        free(result[i]);
    }

    free(result);
    free(returnColumnSizes);

    return 0;
}

算法分析

该算法的时间复杂度为 O(n^3)，其中 n 是数组 nums 的大小。排序的时间复杂度为 O(nlogn)，三重循环遍历的时间复杂度为 O(n^3)。

空间复杂度为 O(1)，算法只使用了常数级别的额外空间。

示例和测试

示例输入1:

nums = [1, 0, -1, 0, -2, 2], target = 0

示例输出1:

Result:
[-2, -1, 1, 2]
[-2, 0, 0, 2]
[-1, 0, 0, 1]

示例输入2:

nums = [], target = 0

示例输出2:

Result:

总结

本文使用C语言实现了解答四数之和问题的代码。通过排序和双指针的方法，我们能够找到所有满足条件且不重复的四元组。该算法的时间复杂度为O(n^3)，空间复杂度为 O(1)。