Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution:

class Solution {
public:
    void process_vector(vector<int>& tmp, vector<pair<int, int> >& nums) {
        for (int i = 0; i < tmp.size(); i++) {
            nums.push_back(make_pair(tmp[i], i));
        }
    }
   
    static bool comp(pair<int, int> first, pair<int, int> second) {
        return first.first < second.first;
    }
   
    vector<int> twoSum(vector<int>& tmp, int target) {
        vector<int> sol;
        vector<pair<int, int> > nums;
        process_vector(tmp, nums);
        sort(nums.begin(), nums.end(), comp);
        if (nums.size() == 0) {
            return sol;
        }
       
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int temp_sum = nums[left].first + nums[right].first;
            if (temp_sum == target) {
                sol.push_back(nums[left].second);
                sol.push_back(nums[right].second);
                return sol;
            } else if (temp_sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return sol;
    }
};