[LeetCode]1. Two Sum

Posted on In Views: Reading time ≈ 2 mins.

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;
}