# Share Accepted O(n) 4ms C solution

• Welcome to share your suggestions for further improvement! :)

``````int *twoSum(int numbers[], int n, int target) {
static int res_c[2] = {0};
//    int *res_c = (int *)malloc(2*sizeof(int));
if(n < 2)
return res_c;
int set[100000] = {0};
for(int i=0; i < n; ++i) {
if(numbers[i] < -50000 || numbers[i] >= 50000)
return res_c;  //in fact: there should return an error
set[numbers[i] + 50000] = i + 1;  //plus 1 to change 0 based index to 1 based index
}
for(int i=0; i<n; ++i) {
if(set[target - numbers[i] + 50000]) {
//            cout << "i=" << i << ", numbers[i]=" << numbers[i] << ", set[numbers[i]]=" << set[numbers[i]] << endl;
res_c[0] = i + 1;  //plus 1 to change 0 based index to 1 based index
res_c[1] = set[target - numbers[i] + 50000];
if(res_c[0] != res_c[1])
break;
}
}
if(res_c[0] == res_c[1])
res_c[0] = res_c[1] = -1;
return res_c;
}``````

• ``````#define SIZE 256

struct hash_table
{
int key;
int value;
};

struct hash_map
{
struct hash_table **ht;
};

struct hash_table* hash_table_int(int key, int value)
{
struct hash_table *h = (struct hash_table*)malloc(sizeof(struct hash_table*));
h->key =key;
h->value = value;
return h;
}

int get_value(struct hash_map *hm, int key)
{
int hash = (key % SIZE);
if (hash<0) {
return -1;
}
while (hm->ht[hash] != NULL && hm->ht[hash]->key != key) {
hash = (hash+1)%SIZE;
}
if (hm->ht[hash] == NULL) {
return -1;
} else {
return hm->ht[hash]->value;
}
}

void put_value(struct hash_map *hm, int key, int value)
{
int hash = (key % SIZE);
if (hash<0) {
return;
}
while (hm->ht[hash] != NULL && hm->ht[hash]->key != key) {
hash = (hash+1)%SIZE;
}
if (hm->ht[hash] != NULL) {
printf("\nDUP\n");
free(hm->ht[hash]);
}
hm->ht[hash] = hash_table_int(key, value);
}

void free_hm(struct hash_map *hm)
{
for (int i=0; i< SIZE; i++) {
if (hm->ht[i] != NULL) {
free(hm->ht[i]);
}
}
free(hm);
}

struct hash_map * new_hm()
{
struct hash_map *hm = (struct hash_map*)malloc(sizeof(struct hash_map*));
hm->ht = (struct hash_table**)malloc(sizeof(struct hash_table*)*SIZE);
for (int i=0; i<SIZE; i++) {
hm->ht[i] = NULL;
}
return hm;
}

int two_sum(int *arr, int len, int target, int *p)
{
int i;
p = (int*)malloc(sizeof(int)*2);

struct hash_map *hm = new_hm();
for (i=0; i<len; i++) {
put_value(hm, arr[i], i);
}
for (int j=0; j<len; j++) {
int val = get_value(hm, target-arr[j]);
if (val != -1) {
p[0] = j+1;
p[1] = val+1;
printf("\n%d %d\n", j, val);
printf("\n%d %d\n", arr[j], target-arr[j]);
free_hm(hm);
return 1;
}
}
free_hm(hm);
return 0;
}``````

• Do you think your solution is better than mine?

• No. I just pasted my solution using hash table

• where did you test the program ? Is it can be judged by leetcode ?

• What if there is same number in the array ? For example, input array is [0, 1, 2, 0] and target is 0 ?

• On leetcode it is giving me "Output Limit Exceeded" error. If I use gcc v4.4.7 compiler it runs and gives valid output for the sample input of the problem "numbers={2, 7, 11, 15}, target=9" and other random samples inputs which I tried.

It would be great if you can help me overcome the error message! Thanks!

PS: My motive to paste the solution was to help googler browse a hash table based solution.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.