Algorithms

Two Sum

Posted by Sherlock Blaze on 2019-01-24

Question

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, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

Code

It’s easy to finish, so just read the code, And I wrote some comments in there.

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
#ifndef _TWOSUM_H_
#define _TWOSUM_H_

int *twoSum(int* nums, int numsSize, int target);
int *betterOne(int* nums, int numsSize, int target);
/*We'll implement this one when we get hashmap*/
int *bestOne(int* nums, int numsSize, int target);
void twoSumTest(int *nums, int numsSize, int target);

#endif /*_TWOSUM_H_*/

#include <stdio.h>
#include <stdlib.h>

// O(n^2)
int*
twoSum(int* nums, int numsSize, int target)
{
	int i = 0;
	int j;
	int* result = (int*)malloc(sizeof(int) * 2);
	for (; i < numsSize; ++i)
	{
		int remain = target - *(nums + i);
		for (j = i + 1; j < numsSize; ++j)
			if (*(nums + j) == remain)
			{
				result[0] = i;
                result[1] = j;
                break;
			}
	}
	return result;
}

// Waste too much space, if we got [0, 1000, 1, 441, 1], we need almost 4.2M, if we got bigger number, it'll take much more. But the cost of space is O(n)
/*int* 
betterOne(int* nums, int numsSize, int target) {
	int i, max, min;
	max = min = nums[0];
	for (i = 0; i < numsSize; ++i)
	{
		if (nums[i] > max) max = nums[i];
		if (nums[i] < min) min = nums[i];
	}
	int *map = (int*)calloc((max - min + 1), sizeof(int));
	int *reval = (int*)malloc(sizeof(int) * 2);

	for (i = 0; i < numsSize; map[nums[i] - min] = ++i)
	{
		int lookfornum = target - nums[i];
		if (lookfornum < min || lookfornum > max) continue;
		int dis = lookfornum - min;
		printf("mapdis= %d\n", map[dis]);
		if (map[dis])
		{
			reval[0] = i;
			reval[1] = map[dis] - 1;
			break;
		}
	}
	free(map);
	printf("in function: %d, %d\n", reval[0], reval[1]);
	return reval;
}*/

void
twoSumTest(int* nums, int numsSize, int target)
{
	int* resultOne = twoSum(nums, numsSize, target);
	// int* resultTwo = betterOne(nums, numsSize, target);
	printf("twoSum result: %d, %d\n", resultOne[0], resultOne[1]);
	// printf("betterOne result: %d, %d\n", resultTwo[0], resultTwo[1]);
	free(resultOne);
	// free(resultTwo);
}

We’ll try a better way when we finish the hash map.


FEATURED TAGS
Algorithms
FRIENDS