【LeetCode #18 题解】 四数之和

一、题目

给定一个包含 n n n 个整数的数组 n u m s nums nums 和一个目标值 t a r g e t target target，
判断 n u m s nums nums 中是否存在四个元素 a ， b ， c 和 d a，b，c 和 d a，b，c和d ，使得 a + b + c + d a + b + c + d a+b+c+d 的值与 t a r g e t target target 相等？

找出所有满足条件且不重复的四元组。

注意：
答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

二、题解

之前做过一个三数之和的题，本题四数之和，
思路也是一样：《【LeetCode #15 题解】 三数之和》

如下图所示，p1、p2、p3 分别是从左向右循环遍历，p4从右向左循环遍历。

相较于普通的算法，该算法优化点在于：

1. 当 p 1 + p 2 + p 3 + p 4 = = t a r g e t p1 + p2 + p3 + p4 == target p1+p2+p3+p4==target时，单独移动 p 3 p3 p3 或 p 4 p4 p4 均不可能相等，所以此时需要同时移到 p 3 p3 p3 和 p 4 p4 p4 这样一增一减才有可能会相等。
2. 当 p 1 + p 2 + p 3 + p 4 > t a r g e t p1 + p2 + p3 + p4 > target p1+p2+p3+p4>target时，需要移到 p 4 p4 p4，这样才会使得左值更小
3. 当 p 1 + p 2 + p 3 + p 4 < t a r g e t p1 + p2 + p3 + p4 < target p1+p2+p3+p4<target时，只需要移到 p 3 p3 p3，这样才会使得左值更大
4. p 1 、 p 2 、 p 3 、 p 4 p1、p2、p3 、p4 p1、p2、p3、p4 在移动时同时做去重处理，避免出来重复计算的情况。

代码如下：

// 打印数组内容
void pintf_array(int *nums, int numsSize, char *s)
{
    int i;
    printf("\n%s ",s);
    for(i = 0 ; i < numsSize; i++)
    {
        printf("%d ", nums[i]);
    }
    printf("\n");
}

// 对数组进行排序
void sort_array(int * nums, int numsSize)
{
    int *left, *right, *mid, *tmp, t;

    left = nums;    // 头指针
    right = nums+numsSize-1;   // 尾指针
    while(left < right)
    {
        mid = left;
        while(mid <= right)
        {
            if(*left > *mid || *mid > *right){
                tmp = *left > *mid ? left : right;
                t = *mid;   *mid = *tmp;  *tmp = t;
            }
            mid++;
        }
        left++;
        right--;
    }
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes){
    if(numsSize < 4){
        *returnSize = 0;
        *returnColumnSizes = 0;
        return NULL;
    }

    int **result, i, num=0;
    result = (int **)malloc(sizeof(int *) * numsSize * numsSize);
    *returnColumnSizes = (int *)malloc(sizeof(int) * numsSize * numsSize);
    
    sort_array(nums, numsSize);
    pintf_array(nums, numsSize, "排序后： ");

    // 定义四个指针，顺序为 left->mid_l->mid_r->right
    int *left=nums, *mid_l, *mid_r, *right=nums+numsSize-1;
    int sum;
    while(left - nums <= numsSize -4)
    {
        sum = 0;
        mid_l = left+1;
        while(mid_l - nums <= numsSize -3){
            mid_r = mid_l+1;
            right = nums + numsSize -1;
            sum = *left + *mid_l;
            while(mid_r < right)
            {   
                if(sum + *mid_r +*right == target){
                    // 找到了, 动态分配内存
                    (*returnColumnSizes)[num] = 4;
                    result[num] = (int *)malloc(sizeof(int) * 4);
                    result[num][0] = *left;
                    result[num][1] = *mid_l;
                    result[num][2] = *mid_r;
                    result[num][3] = *right;
                    num++;
                    printf("找到 %2d  %2d  %2d  %2d = %2d\n",*left, *mid_l, *mid_r, *right, target);

                    // 同时向中间移动一个数, 且去重
                    mid_r++;
                    while(mid_r<right && *mid_r == *(mid_r-1))mid_r++;
                    right--;
                    while(mid_r<right && *right == *(right+1))right--;
                }else if(sum + *mid_r +*right > target){
                    right--;
                    while(mid_r<right && *right == *(right+1))right--;
                }else{
                    mid_r++;
                    while(mid_r<right && *mid_r == *(mid_r-1))mid_r++;
                }
            }
            mid_l++;
            while(mid_l<right && *mid_l == *(mid_l-1))mid_l++;
        }
        left++;
        while(left - nums <= numsSize -4 && *left == *(left-1))left++;
    }

  
    *returnSize = num;
    return result;
}

输入：
[-3,-2,-1,0,0,1,2,2,3,3]
0

输出：
[[-3,-2,2,3],[-3,-1,1,3],[-3,-1,2,2],[-3,0,0,3],[-3,0,1,2],[-2,-1,0,3],[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

stdout：
排序后：  -3 -2 -1  0  0  1  2  2  3  3 
找到 -3  -2   2   3 =  0
找到 -3  -1   1   3 =  0
找到 -3  -1   2   2 =  0
找到 -3   0   0   3 =  0
找到 -3   0   1   2 =  0
找到 -2  -1   0   3 =  0
找到 -2  -1   1   2 =  0
找到 -2   0   0   2 =  0
找到 -1   0   0   1 =  0