Day 6, 1, Two Sum

Two Sum
Solution #1, sort then look for match, O(nlogn)

struct Node {
  int val;
  int index;
  Node(){}
  Node(int v,int i):val(v),index(i) {}
};

bool comp (const Node &left, const Node &right) {
    return left.val < right.val;
}

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<Node> boo;
        for (int i=0;i<numbers.size();i++) {
            boo.push_back(Node(numbers[i],i+1));
        }
        sort(boo.begin(),boo.end(),comp);
        
        int frontI = 0;
        int backI = boo.size() - 1;
        while (frontI < backI) {
            int sum = boo[frontI].val + boo[backI].val;
            if (sum == target) {
                int minI = min(boo[frontI].index,boo[backI].index);
                int maxI = max(boo[frontI].index,boo[backI].index);
                vector<int> re;
                re.push_back(minI);
                re.push_back(maxI);
                return re;
            }
            else if (sum < target) {
                frontI++;
            }else {
                backI--;
            }
        }
    }
};

Solution #2, hashmap, O(n)

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        unordered_map<int,int> mapping;
        vector<int> result;
        for (int i=0;i<numbers.size();i++) {
            if (mapping.find(numbers[i]) == mapping.end()) {
                mapping[numbers[i]] = i + 1;
            }else if (numbers[i] * 2 == target) {
                result.push_back(mapping[numbers[i]]);
                result.push_back(i+1);
                return result;
            }
        }
         
        for (int i=0;i<numbers.size();i++) {
            int remainder = target - numbers[i];
            if (remainder * 2 != target && mapping.find(remainder) != mapping.end()) {
                result.push_back(i+1);
                result.push_back(mapping[remainder]);
                return result;
            }
        }
        
        return result;
    }
};

Added on Sep-02-2014 
Solution #3

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        vector<int> ret(2);
        unordered_map<int,int> mapping;
        unordered_map<int,int>::iterator itr;
        
        for (int i = 0; i < numbers.size(); i++) {
            itr = mapping.find(numbers[i]);
            if (itr == mapping.end()) {
                mapping.insert(make_pair(numbers[i],i + 1));
            }else {
                if (numbers[i] + itr->first == target) {
                    ret[0] = itr->second;
                    ret[1] = i + 1;
                    return ret;
                } 
            }
        }
        
        for (int i = 0; i < numbers.size(); i++) {
            itr = mapping.find(target - numbers[i]);
            if (itr != mapping.end() && itr->second != i + 1) {
                ret[0] = i + 1;
                ret[1] = itr->second;
                return ret;
            }
        }
        
        return ret;
    }
};