三数之和：C 语言双指针解法详解

三数之和：C 语言双指针解法详解

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

例如，输入 [-1, 0, 1, 2, -1, -4]，输出 [[-1, 0, 1], [-1, -1, 2]]。

核心难点

解决这道题主要面临两个挑战：一是如何高效地存储结果并避免重复，二是如何在保证正确性的前提下降低时间复杂度。暴力枚举的时间复杂度为 O(n³)，容易超时，因此需要更优的策略。

解题思路

1. 排序预处理

首先对数组进行升序排序。排序后，相同的数字会相邻，这为后续的去重操作提供了便利。虽然冒泡排序实现简单，但在数据量较大时效率不如快速排序，不过对于理解双指针逻辑来说足够清晰。

2. 双指针扫描

固定第一个数 nums[i]，然后使用两个指针 begin 和 end 分别指向剩余部分的头部和尾部。

• 如果三数之和等于 0，记录结果，并向内移动两个指针。
• 如果和大于 0，说明右端数值过大，end 左移。
• 如果和小于 0，说明左端数值过小，begin 右移。

3. 去重处理

为了避免重复三元组，需要在循环中跳过相同的数字：

• 外层循环中，若当前数字与前一个相同，则跳过。
• 找到有效组合后，移动指针时需跳过所有连续相同的值。

代码实现

以下是完整的 C 语言实现，包含动态内存分配和必要的注释说明。

/**
 * Return an array of arrays of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */

/* 冒泡排序辅助函数 */
void bubblesort(int *nums, int numsSize) {
    int i, j;
    int temp;
    int flag = 1;
    
    for (i = 0; i < numsSize; i++) {
        for (j = 0; j < numsSize - 1; j++) {
            if (nums[j + 1] < nums[j]) {
                temp = nums[j + 1];
                nums[j + 1] = nums[j];
                nums[j] = temp;
                flag = 0;
            }
        }
        if (flag == 1)
            break;
    }
}

int** threeSum(int* nums, int numsSize, int* returnSize) {
    // 预估最大空间，实际使用时根据返回数量调整
    int** result = (int**)malloc(sizeof(int*) * (numsSize * (numsSize - 1) * (numsSize - 2)) / 6);  
    int i, begin, end;
    int m = 0;
    int sum;
    
    if (numsSize < 3) {
        *returnSize = 0;
        return NULL;
    }
    
    // 先排序
    bubblesort(nums, numsSize);

    for (i = 0; i < numsSize - 2; i++) {
        // 优化：如果当前数大于 0，后面不可能和为 0
        if (nums[i] > 0)
            break;
        
        // 去重：跳过重复的第一个数
        if (i > 0 && nums[i] == nums[i - 1])
            continue;
            
        begin = i + 1;
        end = numsSize - 1;
        
        while (begin < end) {
            sum = nums[i] + nums[begin] + nums[end];
            
            if (sum == 0) {
                // 分配单个三元组的空间
                result[m] = (int*)malloc(sizeof(int) * 3);  
                result[m][0] = nums[i];
                result[m][1] = nums[begin];
                result[m][2] = nums[end];
                m++;
                
                begin++;
                end--;
                
                // 去重：跳过重复的第二个数
                while (begin < end && nums[begin] == nums[begin - 1]) {
                    begin++;
                }
                // 去重：跳过重复的第三个数
                while (begin < end && nums[end] == nums[end + 1]) {
                    end--;
                }
            } else if (sum > 0) {
                end--;
            } else {
                begin++;
            }
        }
    }
    
    *returnSize = m;  
    return result;       
}

注意事项

1. 内存管理：C 语言中手动管理内存是关键。这里使用了 malloc 分配二维数组结构，调用方需负责释放内存。
2. 边界检查：当数组长度小于 3 时直接返回空结果，避免非法访问。
3. 性能权衡：示例中使用冒泡排序是为了展示基础逻辑，实际工程中建议使用标准库中的 qsort 以获得更好的性能。

---

这个方案将时间复杂度优化到了 O(n²)，空间复杂度取决于结果集的大小。通过合理的去重逻辑，确保了输出的唯一性。