四数之和问题C代码超时求助：如何优化现有算法？

问题描述 #

给定一个包含n个整数的数组nums，需返回所有满足以下条件的唯一四元组[nums[a], nums[b], nums[c], nums[d]]：

1. 0 ≤ a, b, c, d < n
2. a、b、c、d互不相同
3. nums[a] + nums[b] + nums[c] + nums[d] == target
   返回顺序不限。

示例 #

示例1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

约束条件 #

• 1 ≤ nums.length ≤ 200
• -10^9 ≤ nums[i] ≤ 10^9
• -10^9 ≤ target ≤ 10^9

原代码问题分析 #

你当前的代码采用三重循环+二分查找的思路，时间复杂度为O(n³logn)，对于n=200的情况，计算量约为8e6 * 8 ≈ 6.4e7，容易触发时间限制。此外代码还存在以下问题：

1. 内存分配错误：ans = realloc(ans, (*returnSize) * sizeof(int)); 应分配sizeof(int*)，因为ans是二维数组，每个元素是int指针。
2. 二分查找范围错误：初始left = k会包含k本身，应该从k+1开始，保证索引互不相同。
3. 元素取值错误：ans[*returnSize - 1][3] = nums[l]; 这里的l是目标值，不是索引，应该直接赋值l。
4. 未处理重复四元组：当数组中有重复元素时，会生成重复结果，不符合题目要求的“唯一四元组”。

优化方案：二重循环+双指针 #

将时间复杂度降至O(n²)，核心思路是：

1. 先对数组排序（保留原步骤）。
2. 遍历前两个数i和j，然后用双指针指向j+1（left）和数组末尾（right），通过调整双指针位置寻找满足nums[i]+nums[j]+nums[left]+nums[right] == target的组合。
3. 全程处理重复元素，避免生成重复四元组。

优化后的C代码 #

#include <stdlib.h>

void quicksort(int *arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            int tmp = arr[++i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    arr[right] = arr[++i];
    arr[i] = pivot;
    quicksort(arr, left, i - 1);
    quicksort(arr, i + 1, right);
}

int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    if (numsSize < 4) return NULL;
    
    quicksort(nums, 0, numsSize - 1);
    int **ans = malloc(0);
    *returnColumnSizes = malloc(0);
    
    for (int i = 0; i < numsSize - 3; i++) {
        // 跳过i的重复元素
        if (i > 0 && nums[i] == nums[i-1]) continue;
        // 剪枝：最小的四个数之和已经大于target，无需继续
        if ((long long)nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target) break;
        // 剪枝：当前i和最大的三个数之和小于target，跳过当前i
        if ((long long)nums[i] + nums[numsSize-1] + nums[numsSize-2] + nums[numsSize-3] < target) continue;
        
        for (int j = i + 1; j < numsSize - 2; j++) {
            // 跳过j的重复元素
            if (j > i + 1 && nums[j] == nums[j-1]) continue;
            // 剪枝：当前i、j和最小的两个数之和大于target，无需继续
            if ((long long)nums[i] + nums[j] + nums[j+1] + nums[j+2] > target) break;
            // 剪枝：当前i、j和最大的两个数之和小于target，跳过当前j
            if ((long long)nums[i] + nums[j] + nums[numsSize-1] + nums[numsSize-2] < target) continue;
            
            int left = j + 1;
            int right = numsSize - 1;
            while (left < right) {
                // 使用long long避免溢出
                long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    // 扩容结果数组
                    *returnSize += 1;
                    ans = realloc(ans, *returnSize * sizeof(int*));
                    ans[*returnSize - 1] = malloc(4 * sizeof(int));
                    ans[*returnSize - 1][0] = nums[i];
                    ans[*returnSize - 1][1] = nums[j];
                    ans[*returnSize - 1][2] = nums[left];
                    ans[*returnSize - 1][3] = nums[right];
                    
                    // 更新列大小数组
                    *returnColumnSizes = realloc(*returnColumnSizes, *returnSize * sizeof(int));
                    (*returnColumnSizes)[*returnSize - 1] = 4;
                    
                    // 跳过left的重复元素
                    while (left < right && nums[left] == nums[left+1]) left++;
                    // 跳过right的重复元素
                    while (left < right && nums[right] == nums[right-1]) right--;
                    // 移动指针寻找下一组
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
    }
    return ans;
}

优化点说明 #

1. 时间复杂度优化：将三重循环改为二重循环+双指针，时间复杂度从O(n³logn)降至O(n²)，对于n=200，计算量约为200²=4e4，远低于原方案。
2. 剪枝操作：添加多组剪枝条件，提前跳过不可能满足条件的循环，减少不必要的计算。
3. 去重处理：在遍历i、j和移动双指针时，跳过重复元素，保证结果唯一。
4. 溢出处理：使用long long计算四数之和，避免int溢出（因为nums[i]可达1e9，四数相加可能超过int范围）。
5. 内存分配修复：正确分配二维数组的内存，避免访问非法地址。

内容的提问来源于stack exchange，提问作者iskander