leetCode-0018_四数之和

Posted on | In |

题目描述

英文题目

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c+ d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

1
2
3
4
5
6
7
8
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]
中文题目

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，**b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

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

示例：

1
2
3
4
5
6
7
8
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

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

解决方法

方法一
  • 描述

思路跟”三数之和“基本没啥区别，就是多加了一层for循环，其他的都一样

  • 源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdlib.h>
#include <string.h>

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

void k_sum(int *nums, int low, int high, int target, int total, int k, int *stack, int len, int **results, int *count) {
    if (k == 2) {
        while(low < high) {
            int diff = target - nums[low];
            if(diff > nums[high]) {
                while (++low < high && nums[low] == nums[low - 1]) {}
            } else if (diff < nums[high]) {
                while (--high > low && nums[high] == nums[high + 1]) {}
            } else {
                stack[len++] = nums[low];
                stack[len++] = nums[high];
                results[*count] = malloc(total * sizeof(int));
                memcpy(results[*count],stack,total * sizeof(int));
                (*count)++;
                len -= 2;
                //过滤重复
                while (++low < high && nums[low] == nums[low - 1]) {}
                while (--high > low && nums[high] == nums[high + 1]) {}
            }
        }
    }
    else {
        for (int i = low; i <= high - k + 1; i++) {
            if (i > low && nums[i] == nums[i - 1]) {
                continue;
            }
            stack[len++] = nums[i];
            k_sum(nums, i + 1, high, target - nums[i],total, k - 1, stack, len, results, count);
            len--;
        }
    }
}

int** fourSum(int* nums, int numsSize, int target, int* returnSize){
    int len = 4;
    if (numsSize < len) {
        return NULL;
    }
    
    qsort(nums,numsSize,sizeof(*nums),compare);
    
    *returnSize = 0;
    int **results = malloc(sizeof(int *) * (((numsSize * (numsSize - 1) * (numsSize - 2))) / (3 * 2 * 1)));
    //临时存储
    int *stack = malloc(len * sizeof(int));
    k_sum(nums, 0, numsSize - 1, target, len, len, stack, 0, results, returnSize);
    
    return results;
}

void test()
{
    int arr[6] = { 1, 0, -1, 0, -2, 2 };
    int count = 0;
    int **ret = fourSum(arr, 6, 0, &count);
    
    if (ret) {
        for (int i = 0; i < count; i++) {
            int *temp = ret[i];
            printf("%d->%d->%d->%d\n",temp[0], temp[1], temp[2], temp[3]);
        }
        
    }
}

题目来源

4Sum

四数之和