Two Sum II - Input Array Is Sorted - Three solutions

Array     Binary Search     Medium     Two Pointers    

Problem Statement:

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

 

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

 

Constraints:

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.
• -1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

Solution:

HashSet:

vector<int> twoSum(vector<int>& numbers, int target) 
{
	unordered_map<int,int> comps;
	for (int i=0; i<numbers.size(); i++)
	{
		if (comps.count(numbers[i])) return {comps[numbers[i]]+1,i+1};
		comps[target-numbers[i]] = i;
	}
	return {};
}

Linear search using two pointers:

vector<int> twoSum(vector<int>& numbers, int target) 
    {
        int lo=0, hi=numbers.size()-1;
        while (lo<hi)
        {
            int curr = numbers[lo]+numbers[hi];
            if (curr==target) return {lo+1,hi+1};
            else if (curr<target) lo++;
            else hi--;
        }
        return {};
    }

Linear traversal + Binary search

vector<int> twoSum(vector<int>& numbers, int target) 
    {
        for (int i=0; i<numbers.size(); i++)
        {
            if (i>0 && numbers[i]==numbers[i-1]) continue;
            int tmp = target-numbers[i], lo=i+1, hi=numbers.size()-1;
            while (lo<=hi)
            {
                int mid = lo + (hi-lo)/2;
                if (numbers[mid]==tmp) return {i+1,mid+1};
                else if (numbers[mid]<tmp) lo=mid+1;
                else hi=mid-1;
            }
        }
        return {};
    }