-
Notifications
You must be signed in to change notification settings - Fork 0
/
twoSum_167.c
71 lines (64 loc) · 1.65 KB
/
twoSum_167.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
#include <stdlib.h>
#include <stdio.h>
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
int *ret = NULL;
*returnSize = 0;
int mid = target/2;
if (target%2 && target < 0) {
mid = target/2 - 1;
}
int l = -1;
int r = -1;
for (int i = 0; i < numbersSize; i++) {
if(numbers[i] > mid) {
r = i;
break;
} else if (numbers[i] <= mid)
{
l = i; // update every iterate to maximum
}
}
if(l > 0 && l < numbersSize && numbers[l] == mid && numbers[l] + numbers[l-1] == target) {
*returnSize = 2;
ret = (int *)malloc(sizeof(int) * 2);
ret[0] = l-1+1;
ret[1] = l+1;
return ret;
}
while (1) {
if (l < 0 || r > (numbersSize - 1)) {
return ret;
}
int sum = numbers[l] + numbers[r];
if (sum == target) {
*returnSize = 2;
ret = (int *)malloc(sizeof(int) * 2);
ret[0] = l+1;
ret[1] = r+1;
return ret;
} else if (sum > target)
{
l--;
} else if (sum < target) {
r++;
}
}
return ret; // impossible here;
}
int numbers[] = {0,0,3,4};
int target = 0;
int main()
{
int size = 0;
int *ret = twoSum(numbers, sizeof(numbers)/sizeof(int), target, &size);
if (ret != NULL) {
printf("numbers[%d] + numbers[%d] == %d.\n", ret[0], ret[1], numbers[ret[0]-1] + numbers[ret[1]-1]);
free(ret);
} else {
printf("no found.\n");
}
return 0;
}