[LeetCode] 167. Two Sum II - Input Array Is Sorted c++

• 문제

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.

 

numbers[index1] + numbers[index2] = target 이 되는 index1 , 2를 구하는 문제이다.

 

• 문제 해결

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