-
Notifications
You must be signed in to change notification settings - Fork 2
/
q0018.c
121 lines (110 loc) · 3.58 KB
/
q0018.c
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
//
// q0018.c
// LeetCode
//
// Created by NowOrNever on 22/10/2019.
// Copyright © 2019 DoubleL. All rights reserved.
//
#include "q0018.h"
#include "../common.h"
//18. 4Sum
//Medium
//754
//146
//
//
//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:
//
//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]
// ]
int** fourSum(int* nums, int numsSize, int target, int* returnSize) {
int bufferSize = 100;
int **result = calloc(bufferSize, sizeof(int *));
int resultCount = 0;
if (numsSize < 4) {
*returnSize = 0;
return result;
}
qsort(nums, numsSize, sizeof(int), compareIntFunction);
// for (int i = 0; i < numsSize; i++) {
// printf(" %d ",nums[i]);
// }
for (int i = 0; i < numsSize ; i++) {
// handle duplicates i
while (i > 0 && nums[i] == nums[i - 1]) {
i++;
}
for (int j = i + 1; j < numsSize; j++) {
while (j > i + 1 && nums[j] == nums[j - 1]) {
j++;
}
int pStart = j + 1;
int pEnd = numsSize - 1;
int sum = INT32_MAX;
while (pStart < pEnd) {
sum = nums[i] + nums[j] + nums[pStart] + nums[pEnd];
if (sum > target) {
pEnd--;
// while (nums[pEnd] == nums[pEnd + 1]) {
// pEnd--;
// }
}else if(sum < target){
pStart++;
// while (nums[pStart] == nums[pStart - 1]) {
// pStart++;
// }
}else{
// printf("\n rescount(%d) i(%d) start(%d) end(%d)", resultCount, i, pStart, pEnd);
if (resultCount >= bufferSize) {
bufferSize += bufferSize;
result = realloc(result, sizeof(int *) * bufferSize);
}
int *newNode = calloc(1, sizeof(int) * 4);
newNode[0] = nums[i];
newNode[1] = nums[j];
newNode[2] = nums[pStart];
newNode[3] = nums[pEnd];
result[resultCount++] = newNode;
pStart++;
while (pStart < pEnd && nums[pStart] == nums[pStart - 1]) {
pStart++;
}
pEnd--;
while (pStart < pEnd && nums[pEnd] == nums[pEnd + 1]) {
pEnd--;
}
}
}
}
}
*returnSize = resultCount;
return result;
}
int question18(){
int numbers[] =
// {0,0,0,0};
// {-1, 0, 1, 2, -1, -4};
// {-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0};
// {1, 0, -1, 0, -2, 2};
// {0,4,-5,2,-2,4,2,-1,4};
{1,-2,-5,-4,-3,3,3,5};
int resultSize = 0;
int **result = fourSum(numbers, sizeof(numbers) / sizeof(int), -11, &resultSize);
for (int i = 0; i < resultSize; i++) {
printf("\n i(%d) %d %d %d %d",i,result[i][0],result[i][1],result[i][2], result[i][3]);
}
printf("\n");
return 0;
}