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

题目

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c，使得 a + b + c = 0。找出所有满足条件且不重复的三元组。

引言

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

算法思路

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

算法的步骤如下：

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

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

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

   • 在 left 和 right 之间进行双指针遍历，判断三个数的和与零的关系：

     • 如果三个数的和为零，将它们添加到结果集中。
     • 如果三个数的和大于零，将 right 向左移动一位。
     • 如果三个数的和小于零，将 left 向右移动一位。
4. 返回结果集 result。

代码实现

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

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

int cmp(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), 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 - 2; i++) {
        if (nums[i] > 0) {
            break;
        }

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

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

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

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

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

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

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

    return result;
}

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

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

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

    free(result);
    free(returnColumnSizes);

    return 0;
}

算法分析

该算法的时间复杂度为 O(n^2)，其中 n 是数组 nums 的大小。排序的时间复杂度为 O(nlogn)，双指针遍历的时间复杂度为 O(n)。

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

示例和测试

示例输入1:

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

示例输出1:

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

示例输入2:

nums = []

示例输出2:

Result:

示例输入3:

nums = [0]

示例输出3:

Result:

总结

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