三数之和的算法实现c语言

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

以下是 C 语言中的一种实现方法：

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

#define MAX_SIZE 1000

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

int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    int i, j, k;
    int count = 0;
    int **res = (int **)malloc(sizeof(int *) * MAX_SIZE);
    int *temp = (int *)malloc(sizeof(int) * 3);
    *returnColumnSizes = (int *)malloc(sizeof(int) * MAX_SIZE);
    qsort(nums, numsSize, sizeof(int), compare);
    for (i = 0; i < numsSize - 2; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        j = i + 1;
        k = numsSize - 1;
        while (j < k) {
            if (nums[i] + nums[j] + nums[k] == 0) {
                temp[0] = nums[i];
                temp[1] = nums[j];
                temp[2] = nums[k];
                res[count] = (int *)malloc(sizeof(int) * 3);
                (*returnColumnSizes)[count] = 3;
                for (int l = 0; l < 3; l++) {
                    res[count][l] = temp[l];
                }
                count++;
                j++;
                k--;
                while (j < k && nums[j] == nums[j-1]) j++;
                while (j < k && nums[k] == nums[k+1]) k--;
            } else if (nums[i] + nums[j] + nums[k] < 0) {
                j++;
            } else {
                k--;
            }
        }
    }
    *returnSize = count;
    free(temp);
    return res;
}

int main() {
    int nums[] = {-1, 0, 1, 2, -1, -4};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int returnSize;
    int *returnColumnSizes;
    int **res = threeSum(nums, numsSize, &returnSize, &returnColumnSizes);
    printf("[\n");
    for (int i = 0; i < returnSize; i++) {
        printf("  [");
        for (int j = 0; j < returnColumnSizes[i]; j++) {
            printf("%d", res[i][j]);
            if (j < returnColumnSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i < returnSize - 1) printf(",");
        printf("\n");
    }
    printf("]\n");
    return 0;
}

这个算法的时间复杂度为 O(N^2)，其中 N 是数组的长度。具体实现是先对数组进行排序，然后枚举第一个数，使用双指针法在剩余部分中查找后两个数，如果和为零则记录答案并移动指针。需要注意的是，为了避免重复的解，需要在枚举第一个数和查找后两个数的过程中进行去重操作。