[LeetCode] 167. Two Sum II - Input array is sorted 문제풀이

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

Two Sum II - Input array is sorted - LeetCode

 

문제 내용

정렬되어 있는 배열에서 2개의 합이 target이랑 일치할 때 배열의 index 2개를 출력

 

문제 풀이

두 숫자의 합을 구하는 것을 target을 뺀 다음에 바이너리 서치로 찾는 방법을 생각했다.

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for (int i = 0; i < numbers.size(); ++i) {
            int v = target - numbers[i];
            int j = lower_bound(numbers.begin()+i+1, numbers.end(), v) - numbers.begin();
            if (j >= numbers.size())
                continue;
            
            if (numbers[j] == v)
                return {i+1, j+1};
        }
        return vector<int>();
    }
};

 

양쪽에서 for문 1번만 수행하면 됐었다.

왼쪽은 증가하는 거고,

오른쪽은 감소하는 것이기 때문에

양쪽에서 타겟 크기에 맞을 때까지 조이면 된다.

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int a = 0;
        int b = numbers.size()-1;
        while (a < b){
            int sum = numbers[a] + numbers[b];
            if (sum < target)
                ++a;
            else if(sum > target)
                --b;
            else
                break;
        }
        return {a+1, b+1};
    }
};