gistfile1.cpp

#define BIGPRIME 4979

class Solution 
{
private:
    typedef struct element
    {
        int value;
        int index;
    }Element;
    
    vector<Element> hash[BIGPRIME];
    
public:
    int positionInHash(int x)
    {
        while (x < BIGPRIME)
            x = x + BIGPRIME;
        int position = x % BIGPRIME;
        return position;
    }
    
    void pushInHash(Element x)
    {
        int position = positionInHash(x.value);
        hash[position].push_back(x);
    }
    
    int findInHash(int x, int j)
    {
        int position = positionInHash(x);
        int count = hash[position].size();
        
        for (int i = 0; i < count; i++)
            if (x == hash[position][i].value && hash[position][i].index != j)
                return hash[position][i].index; // return true
        return -1; // return false
    }
    
    void popFromHash(Element x)
    {
        int position = positionInHash(x.value);
        int count = hash[position].size();
        bool found = false;
        int i;
        
        for (i = 0; i < count && (!found); i++)
            if (x.value == hash[position][i].value && 
                x.index == hash[position][i].index)
                found = true;
        
        if (found)
        {
            i--;
            hash[position][i] = hash[position][hash[position].size() - 1];
            hash[position].pop_back();
        }
    }
    
    vector<int> twoSum(vector<int> &numbers, int target) 
    {
        vector<int> result;
        int count = numbers.size();
        Element x;
        
        for (int i = 0; i < count; i++)
        {
            x.value = numbers[i];
            x.index = i;
            
            pushInHash(x);
        }
        
        for (int i = 0; i < count; i++)
        {
            int element = numbers[i];
            int difference = target - element;
            int index_find = findInHash(difference, i); // the returned value to be different from i
            
            if (index_find > -1)
            {
                result.push_back(i + 1);
                result.push_back(index_find + 1);
                break;
            }
        }
        
        sort(result.begin(), result.end());
        
        return result;
    }
};