[LeetCode]1. Two Sum

Problem

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:

1
2
3
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution

对数组排序后,第一个数字从数组开始遍历,二分查找满足条件的第二个数字,返回2个数字的位置。
由于排序导致数字位置发生了变换,因此需要一个数组记录变化后第i个数字之前的位置numsLocation[i]

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
#include <assert.h>
#include <stdlib.h>

int* sort(int* nums, int numsSize) {
int *numsLocations = (int *)malloc(sizeof(int) * numsSize);
int i = 0, j = 0;
for(i = 0; i < numsSize; i++)
numsLocations[i] = i;

for(i = 0; i < numsSize; i++) {
int sorted = 1;
for(j = 0; j < numsSize-1; j++) {
if(nums[j] > nums[j+1]) {
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
sorted = 0;
temp = numsLocations[j];
numsLocations[j] = numsLocations[j+1];
numsLocations[j+1] = temp;
}
}
if(sorted)
break;
}
return numsLocations;
}

int find(int* nums, int num, int start, int end) {
if(start > end)
return -1;
int i = (start+end)/2;
if(num > nums[i])
return find(nums, num, i+1, end);
else if(num < nums[i])
return find(nums, num, start, i-1);
return i;
}

/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target) {
int *numsLocations = sort(nums, numsSize);
int i = 0;
int num;
int *locations = (int *)malloc(sizeof(int) * 2);
int j;
for(i = 0; i < numsSize; i++) {
num = nums[i];
if((j=find(nums, target-num, i+1, numsSize-1)) >= 0) {
locations[1] = numsLocations[j];
locations[0] = numsLocations[i];
return locations;
}
}
return NULL;
}

int main() {
int nums[4] = {2, 7, 11, 15};
int *locations = twoSum(nums, 4, 9);
assert(locations[0] == 0);
assert(locations[1] == 1);

int nums2[3] = {5, 75, 25};
locations = twoSum(nums2, 3, 100);
assert(locations[0] == 2);
assert(locations[1] == 1);

return 0;
}