leetcode-18. 四数之和-20220822

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
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]]

思考过程：这个题目和三数之和很相似，不过就是在三数之和的基础上再套了一层循环，然后就可以出来一个整体思路，但是具体的去重和剪枝操作的细节与三数之和不同，所以需要注意去重和剪枝操作

上代码~

/**
 * 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().
 */
 // 使用哈希表，感觉可以找出来所有的可以实现target的答案，但是如何去重是个很难整的问题？ 如果要是不考虑去重的话，可以使用哈希表做
 // 方法一
 // 是否可以通过转换将题目的四数之和转换成三数之和呢？  // 有个大前提就是要对nums进行从大到小的排序
 // a + b + c + d = target
// b + c + d = target - a
// 这样转换一下变成了三数之和,时间复杂度变成O（n^3）
// 对数组进行排序
// 最外面一层循环遍历a
// 进行剪枝和去重
// 下来一层循环遍历b
// 进行剪枝和去重
// 然后双指针遍历c和d
// 移动c和d
// 进行剪枝和去重


void quick_sort(int* nums, int left, int right)
{
    if (left >= right) return;
    int mid;
    mid = partiation(nums, left, right);
    quick_sort(nums, left, mid - 1);
    quick_sort(nums, mid + 1, right);
}

int partiation(int* nums, int left, int right)
{
    int key = nums[left];
    int start = left;
    int end = right;
    int tmp;
    while (start < end) {
        while(start < end && nums[end] >= key) end--;
        while(start < end && nums[start] <= key) start++;
        if (start < end) {
            tmp = nums[end];
            nums[end] = nums[start];
            nums[start] = tmp;
        }
    }
    tmp = nums[start];
    nums[start] = nums[left];
    nums[left] = tmp;
    return end;
}

int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes){
    // 对数组进行排序
    quick_sort(nums, 0, numsSize - 1);
    // 最外面一层循环遍历a
    int a, b, c, d;
    int** ans = (int**)malloc(sizeof(int*) * 2400);
    *returnSize = 0;
    int* col = (int*)malloc(sizeof(int) * 2400);
    *returnColumnSizes = col;
    for(a = 0; a < numsSize; a++) {
        // 进行剪枝和去重
        if (nums[a] > target && nums[a] >= 0 && target >= 0) break; // 剪枝
        if (a > 0 && nums[a] == nums[a - 1]) continue; // 去重
        // 下来一层循环遍历b
        for (b = a + 1; b < numsSize; b++) {
        // 进行剪枝和去重
        if (nums[a] + nums[b] > target && nums[a] + nums[b] >= 0 && target >= 0) break; // 剪枝
        if (b > a + 1 && nums[b] == nums[b - 1]) continue; // 去重
            // 然后双指针遍历c和d
            c = b + 1;
            d = numsSize - 1;
            while(c < d) {
                // 对abcd四个数指向的位置的数进行判断，等于target的时候收集结果 
                long long int sum = (long long)nums[a] + (long long)nums[b] + (long long)nums[c] + (long long)nums[d]; // 注意防止溢出
                // 进行cd的移动
                if (sum > target) d--;
                if (sum < target) c++;
                if (sum == target) {
                    ans[*returnSize] = (int*)malloc(sizeof(int) *4);
                    ans[*returnSize][0] = nums[a];
                    ans[*returnSize][1] = nums[b];
                    ans[*returnSize][2] = nums[c];
                    ans[*returnSize][3] = nums[d];
                    col[*returnSize] = 4;
                    (*returnSize)++;
                    // 对cd进行去重的操作
                    while(c < d && nums[d] == nums[d - 1]) d--;
                    while(c < d && nums[c] == nums[c + 1]) c++;
                    // 进行cd的移动
                    d--;
                    c++;
                }
            }
        }
    }
    return ans;
}
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

总结：
1、基础算法要多写多用，我今天写快速排序就感觉很流程了
2、多独立思考，尽量自己先做，然后再去看教程讲解就好一些
3、注意细节判断，流程思考清楚以后，细节判断要仔细，不然找错误的地方比较耗费时间