Two Number Sum

• Time : O(n)
• Space : O(n)

vector<int> twoNumberSum(vector<int> array, int targetSum) {
    unordered_set<int> us;
    for(auto& a : array) {
        if(us.count(targetSum - a))
            return {a, targetSum - a};
        us.insert(a);
    }
    return {};
}

• Time : O(nlogn)
• Space : O(1)

vector<int> twoNumberSum(vector<int> array, int targetSum) {
    sort(begin(array), end(array));
    int l = 0, r = array.size() - 1;
    while(l < r) {
        int sum = array[l] + array[r];
        if(sum == targetSum) return {array[l], array[r]};
        else if(sum < targetSum) l++;
        else r--;
    }
    return {};
}