Two sum 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 two numbers such that they add up to the target. You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: value1 = 2, value2 = 7

1. bruteforce solution: 

The complexity is O(N^2):

[code]

bool bruteforce(vector<int> &v, int target, int &x, int &y)
{
    // O(N^2)
    for(int i = 0; i< v.size(); i++) {
       for(int j= i+1; j< v.size(); j++) {
            if(target == v[i] + v[j]) {
                 x = v[i];
                 y = v[j];
                 return true;
            }
       }
    }
    return false;
}

2. Sort and find solution: 

The Complexity is O(Nlog(N)) majorly because of sort complexity.

[code]

bool sortandfind(vector<int> &v, int target, int &x, int &y)
{
    sort(v.begin(), v.end());   // O(NlogN)
    int i = 0;
    int j = v.size() - 1;

    while(i<j) {
       if (v[i] + v[j] > target) j--;
       if (v[i] + v[j] < target) i++;
       if (v[i] + v[j] == target) {
           x = v[i]; y = v[j];
           return true;
       }
    }
    return false;
}

3. map and find solution:

The complexity is O(Nlog(N)) , the same as the above solution.

[code]
bool mapandfind(vector<int> &v, int target, int &x, int &y)
{
     map<int, int> Nap;    // O(Nlog(N))
     for( int i= 0; i< v.size(); i++) {
         Nap.insert(make_pair(target - v[i], v[i]));
     }

     for( int i= 0; i< v.size(); i++) {  // N
         if(Nap.find(v[i]) != Nap.end()) {  // O(log(N))
            x = v[i];
            y = target - v[i];
            return true;
         }
    }
    return false;
}

4. hash (unordered_map) map and find solution:

Just simply change to use hash-map (unordered_map) from above solution, the complexity becomes O(N).

[code]
bool unorderedmapandfind(vector<int> &v, int target, int &x, int &y)
{
     unordered_map<int, int> Nap;    
     for( int i= 0; i< v.size(); i++) {
         Nap.insert(make_pair(target - v[i], v[i]));
     }

     for( int i= 0; i< v.size(); i++) {  // N
         if(Nap.find(v[i]) != Nap.end()) {  // O(1)
            x = v[i];
            y = target - v[i];
            return true;
         }
    }
    return false;
}