问题描述

给一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。 注意：答案中不可以包含重复的三元组。

实现源码

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

// 比较函数用于快速排序
int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    *returnColumnSizes = NULL;
    
    // 处理边界情况
    if (numsSize < 3) return NULL;

    // 对原始数组排序（关键预处理步骤）
    qsort(nums, numsSize, sizeof(int), compare);

    // 初始化结果存储
    int capacity = 16; // 初始容量
    int** result = (int**)malloc(capacity * sizeof(int*));
    *returnColumnSizes = (int*)malloc(capacity * sizeof(int));

    // 主算法逻辑
    for (int i = 0; i < numsSize - 2; ++i) {
        // 跳过重复的第一个元素
        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) {
                // 找到有效三元组
                if (*returnSize >= capacity) {
                    // 动态扩容
                    capacity *= 2;
                    result = realloc(result, capacity * sizeof(int*));
                    *returnColumnSizes = realloc(*returnColumnSizes, capacity * sizeof(int));
                }
                
                // 存储结果
                result[*returnSize] = (int*)malloc(3 * sizeof(int));
                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 nums1[] = {-1,0,1,2,-1,-4};
    int size1 = sizeof(nums1)/sizeof(nums1[0]);
    int returnSize;
    int* returnColumnSizes;
    
    int** result = threeSum(nums1, size1, &returnSize, &returnColumnSizes);
    
    printf("找到 %d 个三元组:\n", returnSize);
    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;
}

算法解析

1. 预处理排序

• 使用快速排序（qsort）将数组升序排列
• 时间复杂度：O(n log n)

2. 三重循环优化为双指针

• 外层循环遍历第一个元素（时间复杂度O(n)）
• 内层使用双指针在排序后的数组中高效查找剩余两个元素（时间复杂度O(n)）

3. 去重策略

• 外层循环跳过重复的第一个元素
• 找到有效三元组后跳过重复的第二个和第三个元素

4. 动态内存管理

• 初始分配16个三元组的空间
• 当空间不足时进行倍增扩容
• 最终需要调用者释放内存

算法分析

时间复杂度

• 最优情况：O(n^2)（排序O(n log n) + 双指针遍历O(n^2)）
• 最坏情况：O(n^2)（所有元素都需要遍历）

空间复杂度

• 额外空间：O(n)（存储结果需要空间）
• 原地修改：是（排序改变原数组）

优缺点

优点

• 时间复杂度显著优于暴力解法的O(n^3)
• 利用排序特性有效跳过重复组合
• 空间复杂度仅与结果数量相关

缺点

• 修改了原始数组顺序
• 需要处理动态内存分配
• 最坏情况下仍需遍历所有可能组合

测试用例说明

1. 常规测试：[-1,0,1,2,-1,-4]

• 期望输出：[[-1,-1,2], [-1,0,1]]
• 验证：正确处理重复元素和多个解的情况

2. 全零测试：[0,0,0]

• 期望输出：[[0,0,0]]
• 验证：正确处理全相同元素的情况

3. 无解测试：[1,2,-2,-1]

• 期望输出：空数组
• 验证：正确识别无解情况

4. 边界测试：[0,0,0,0]

• 期望输出：[[0,0,0]]
• 验证：正确处理多个重复解的去重

该实现通过排序预处理和双指针技巧，在保证效率的同时正确处理了重复组合问题，是解决三数之和问题的经典方案。