Code : Two Sum

class Solution {
  public:
    vector<int> twoSum(vector<int> &a, int target);
};

vector<int> Solution::twoSum(vector<int> &a, int target) {
    int n = a.size();
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        int need = target - a[i];
        if (mp.find(need) != mp.end()) {
            return {i, mp[need]};
        }
        mp[a[i]] = i;
    }

    return {-1, -1};
}

class Solution {
  public:
    vector<int> twoSum(vector<int> &a, int target);
};

vector<int> Solution::twoSum(vector<int> &a, int target) {
    int n = a.size();
    vector<pair<int, int>> store(n);
    for (int i = 0; i < n; i++) {
        store[i] = {a[i], i};
    }
    sort(store.begin(), store.end());

    for (int i = 0; i < n; i++) {
        auto need = make_pair(target - store[i].first, -1);
        auto itr = lower_bound(store.begin() + i + 1, store.end(), need);
        if (itr != store.end() && itr->first == need.first) {
            return {store[i].second, itr->second};
        }
    }

    return {-1, -1};
}