(Leet Code c++)Two Sum(2) - Input array is sorted

167. Two Sum II - Input array is sorted

 

Given an 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.

Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.length.

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

 

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.

Example 2:

Input: numbers = [2,3,4], target = 6 Output: [1,3]

Example 3:

Input: numbers = [-1,0], target = -1 Output: [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.

이진 탐색으로 두 수의 합이 target인 인덱스의 위치를 찾으면 된다.

인덱스는 각각 +1을 해주어 답과 같도록 하면 된다.

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        vector<int> answer(2, 0);
        
        for(int i = 0; i < numbers.size(); i++){
            int front = i + 1;
            int back = numbers.size() - 1;
            int diff = target - numbers[i];
            
            while(front <= back){
                int mid = (front + back) / 2;
                
                if(numbers[mid] == diff){
                    answer[0] = i + 1;
                    answer[1] = mid + 1;
                    
                    return answer;
                }
                else if(numbers[mid] < diff){
                    front = mid + 1;
                }
                else{
                    back = mid - 1;
                }
            }
        }
        
        return answer;
    }
};