-
Notifications
You must be signed in to change notification settings - Fork 1
/
3Sum cleanCode.c
106 lines (87 loc) · 2.2 KB
/
3Sum cleanCode.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
#include <stdio.h>
#include <stdlib.h>
int comp(const void *a,const void *b)
{
return *(int *)a - *(int *)b;
}
// refer from https://leetcode.com/problems/3sum/discuss/142616/clean-C-solution
int** threeSum(int* nums, int numsSize, int* returnSize)
{
// sort
if (numsSize < 3 || nums == NULL)
{
return NULL;
}
qsort(nums,numsSize,sizeof(int),comp);
int i;
*returnSize = 0;
// you need assign the ret is NUll,otherwise realloc the ret will be wrong
int **ret = NULL;
for (i = 0; i < numsSize; i++)
{
int start = i + 1;
int end = numsSize - 1;
int sum;
//handles duplicates for i position
if (i > 0 && nums[i] == nums[i-1])
{
continue;
}
while (start < end)
{
sum = nums[i] + nums[start] + nums[end];
if (sum == 0)
{
(*returnSize)++;
ret = (int **)realloc(ret,sizeof(int *) * (*returnSize));
int key = (*returnSize) - 1;
ret[key] = malloc(3 * sizeof(int));
ret[key][0] = nums[i];
ret[key][1] = nums[start];
ret[key][2] = nums[end];
while (start < end && nums[start] == nums[start+1])
{
start++;
}
while (start < end && nums[end] == nums[end-1])
{
end--;
}
start++;
end--;
}
else if (sum > 0)
{
end--;
}
else
{
start++;
}
}
}
return ret;
}
int main()
{
int **ret,*arr,size,i,j,len;
puts("请输入你要输入元素的个数");
scanf("%d",&len);
arr = malloc(len * sizeof(int));
puts("请输入每个元素的值");
for (i = 0; i < len; i++)
{
scanf("%d",&arr[i]);
}
ret = threeSum(arr,len,&size);
printf("size is %d\n",size);
for (i = 0; i < size; i++)
{
for (j = 0; j < 3; j++)
{
printf("%d ",ret[i][j]);
}
printf("\n");
}
return 0;
}