Leetcode - 167. Two Sum II - Input Array Is Sorted

문제

오름차순 정렬된 배열이 주어진다. 두 값을 더했을때 target이 되는 index 두개를 리턴하라. 공간복잡도는 O(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].

아디이어

• 해시테이블을 사용 O(n)에 해결가능. 하지만 공간복잡도도 O(n) 이 되기 때문에 그렇게 풀수 없다.
• 문제에서 정렬이 되었다는것은 항상 어떤 해결 책을 적용하라는 의미이다.
• 여기서 two pointer를 사용하여 O(n)/O(1)에 해결을 할수 있다.
  • left포인터는 0번째 인덱스부터 시작하여 항상 커질수만 있고, right 포인터는 마지막 인덱스부터 감소만 할수 있다.
  • 때문에 두 포인터의 합이 target보다 크다면 right--
  • 합이 target보다 작다면 left++ 하여 target이 되는 값을 찾는다.

풀이

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