Two Sum II - Input Array Is Sorted

LeetCode 167. Two Sum II - Input Array Is Sorted

원문

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.

풀이

이미 배열이 감소하지 않는 순서로 정렬이 되어 있으므로 가장 양 끝의 값을 더한 것부터 비교한다.
만약 목표값보다 더한 값이 작다면 앞쪽을 가리키던 인덱스를 1 키운다. 반대로 큰 경우 뒤쪽을 가리키던 인덱스에서 1을 뺀다. 같다면 두 인덱스에 각각 1을 더한 값을 원소로 가지는 배열을 반환한다.

코드

Python

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        lo, hi = 0, len(numbers) - 1

        while lo < hi:
            temp = numbers[lo] + numbers[hi]
            if temp < target: lo += 1
            elif temp > target: hi -= 1
            else: return [lo + 1, hi + 1]

Java

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int lo = 0;
        int hi = numbers.length - 1;

        while (lo < hi) {
            int chk = numbers[lo] + numbers[hi];
            if (chk == target) {
                break;
            } else if (chk < target) {
                lo++;
            } else {
                hi--;
            }
        }

        int[] result = {lo + 1, hi + 1};
        return result;
    }
}