LeetCode Problem : Two Sum

Problem

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

Code

class HashTable32
{
    static const unsigned int A = 2654435769;
    static const int m = 1024;
    int hash(unsigned int key);
    struct Node
    {
        int val;
        int index;
        Node* next;
        Node(int k,int i):val(k),index(i),next(0){}
    };
    Node* Bucket[m];
    public:
    HashTable32();
    ~HashTable32();
    void insert(int key,int i);
    bool find(int key,int j,int& index);
    bool find_r(int key,int j);
};


int HashTable32::hash(unsigned int key)
{
    int result = ((A*key)>>(sizeof(int)*CHAR_BIT - 10));
    return result;
}
HashTable32::HashTable32()
{
    for(int i = 0; i < m; ++i)
        Bucket[i] = 0;
}
HashTable32::~HashTable32()
{
    for(int i = 0; i < m; ++i){
        Node* node = Bucket[i];
        while(node){
            Node* temp = node->next;
            delete node;
            node = temp;
        }
    }
}
void HashTable32::insert(int key,int i)
{
    int hashVal = hash(key);
    Node* temp = new Node(key,i);
    temp->next = Bucket[hashVal];
    Bucket[hashVal] = temp;
}
bool HashTable32::find(int key,int j,int& index)
{
    int hashVal = hash(key);
    Node* node = Bucket[hashVal];
    if(!node){
        return false;
    }
    while(node){
        if(node->val == key && node->index > j){
            index = node->index;
            return true;
        }
        node = node->next;
    }
    return false;
}

bool HashTable32::find_r(int key,int j)
{
    int hashVal = hash(key);
    Node* node = Bucket[hashVal];
    if(!node){
        return false;
    }
    while(node){
        if(node->val == key && node->index == j)
        return true;
        node = node->next;
    }
    return false;
}

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        vector<int> result;
        int n = numbers.size();
        HashTable32 htbl;
        for(int i = 0;i < n; ++i){
            htbl.insert(numbers[i],i + 1);
        }
        for(int i = 0;i < n - 1; ++i){
            int index;
            if(htbl.find(target - numbers[i],i + 1,index)){
                result.push_back(i+1);
                result.push_back(index);
                return result;
            }
        }
        return result;
    }
};