Leetcode Problem 1 - Two Sum

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]

Solution in C

Suppose a+b = target 

                a = target - b

     

insert target - b in map and while lookup if we find a then we got a pair.

The idea is to create a map in C.  

typedef struct map_ {
    int num;
    int index;
    struct map_ *next;
}map_t;

#define MAX_KEY     1000
map_t *table[MAX_KEY] , *neg_table[MAX_KEY];

map_t *alloc_map() {
    map_t *elem = (map_t *)calloc(1, sizeof(map_t));
    return elem;
}

void init_map() {
    int i;
   
    for(i = 0; i < MAX_KEY; i++) {
        table[i] = NULL;
        neg_table[i] = NULL;
    }
}

void insert_pos_elem(int num, int index) {
    int key = 0;
    
    key = num % MAX_KEY;
    map_t *head = table[key], *tmp;
    
    if (head == NULL) {
        table[key] = alloc_map();
        table[key]->num = num;
        table[key]->index = index;
    } else {
        tmp = alloc_map();
        tmp->num = num;
        tmp->index = index;
        tmp->next = head;
        
        table[key] = tmp;
    }
}

void insert_neg_elem(int num, int index) {
    int key = 0;
    
    key = num % MAX_KEY;
    map_t *head = neg_table[key], *tmp;
    
    if (head == NULL) {
        neg_table[key] = alloc_map();
        neg_table[key]->num = num;
        neg_table[key]->index = index;
    } else {
        tmp = alloc_map();
        tmp->num = num;
        tmp->index = index;
        tmp->next = head;
        
        neg_table[key] = tmp;
    }
}

void insert_elem(int num, int index) {
    if (num < 0) {
        num = 0 - num;
        insert_neg_elem(num, index);
    } else {
        insert_pos_elem(num, index);
    }
}


map_t *lookup_elem(int num) {
    int key = 0;
    map_t *head = table[key];
    
   if (num < 0) {
        num = 0 - num;
        key = num % MAX_KEY;
        head = neg_table[key];
   } else {
        key = num % MAX_KEY;
        head = table[key];
   }
    
    while(head != NULL) {
        if (head->num == num)
            return head;
        head = head->next;
    }
    return NULL;
}

int * twoSum(int* nums, int numsSize, int target) {
    int i, n1, *ret = NULL;
    map_t *elem = NULL;
    
    if (nums == NULL)
        return NULL;
    
    init_map();
    
    for (i = 0; i < numsSize; i++) {
        elem = lookup_elem(nums[i]);
        if (elem == NULL) {
            insert_elem((target - nums[i]), i);
        } else {
            n1 = elem->index;
            ret = (int *)calloc(2, sizeof(int));
            ret[0] = n1;
            ret[1] = i;
            return ret;
        }
    }
    
    return ret;
}

Solution in cpp

class Solution {
public:
    vector twoSum(vector& nums, int target) {
        std::vector < int > v;
        std::map < int, int > m;
        std::vector < int >::iterator it;

        for (it = nums.begin(); it != nums.end(); it++) {
           
            m[target - *it] = it - nums.begin();
        }

        std::map < int, int >::iterator m_it;
        for (it = nums.begin(); it != nums.end(); it++) { 
            m_it = m.find(*it);
            if (m_it == m.end())
                continue;
            int index = it - nums.begin();
            if (index ==  m_it->second)
                continue;
            v.push_back(m_it->second);
            v.push_back(it - nums.begin());
            break;
        }
        return v; 
    }

};

Solution in python:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        dic={}
        res=[]
        for i in range(len(nums)):
            dic[target - nums[i]]=i
        print (dic)
        for i in range(len(nums)):
            if nums[i] in dic:
                if i == dic[nums[i]]:
                    continue
                res.append(i)
                res.append(dic[nums[i]])
                break

        return res