LeetCode-167 Two SUM II - Input Array Is Sorted

문제

오름차순으로 정렬된 int형 배열이 주어졌을 때, 배열의 두 요소를 더한 값이 target인 요소들의 인덱스를 구하는 문제입니다. 주어진 자료형이 배열이고, 한쌍의 값을 충족시키는 경우를 찾는 문제이기 때문에 Two Pointers를 적용해 볼 수 있습니다. 

풀이

첫번째 풀이입니다. 배열의 맨 첫번째 요소를 startIdx, 그 다음 요소를 endIdx로 설정합니다. 

1. endIdx로 startIdx의 바로 다음요소부터 배열의 가장 오른쪽까지 조회합니다.

2. 이 과정에서 두 요소의 합이 target과 같다면 각각 인덱스를 반환합니다.

3. 이 과정에서 두 요소의 합이 target보다 작다면 계속해서 endIdx를 +1 해가며 endIdx가 배열의 끝까지 갈때까지 조회합니다.

4. endIdx가 배열의 끝까지 조회하였지만 두 요소의 합이 계속해서 target보다 작은 경우 startIdx를 +1 합니다.

5. 마찬가지로 startIdx가 배열의 맨오른쪽에서 바로 전 요소로 갈때까지 1부터 4까지 반복합니다.

 

이 방법이 틀리진 않았으나, 시간이 너무 오래걸려 Time Limit Exceeded 되었습니다. 

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        startIdx = 0
        endIdx = 1
        while startIdx < len(numbers):
            while endIdx < len(numbers):
                if numbers[startIdx] + numbers[endIdx] == target:
                    return [startIdx+1,endIdx+1]
                elif numbers[startIdx] + numbers[endIdx] < target:
                    endIdx += 1
                else:
                    break
            startIdx += 1
            endIdx = startIdx+1

두번째 방법은 단순하게 endIdx를 startIdx바로 다음으로 설정해두는 것이 아니라 배열의 가장 오른쪽으로 설정해두는 것 입니다. endIdx가 배열의 가장 끝에서 시작하기 때문에 매 실행시마다 endIdx를 +1하는 것이 아닌 -1 해야합니다. 

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        startIdx = 0
        endIdx = len(numbers) - 1
        while startIdx < endIdx:
            if numbers[startIdx] + numbers[endIdx] == target:
                return [startIdx+1,endIdx+1]
            elif numbers[startIdx] + numbers[endIdx] > target:
                endIdx -= 1
            else:
                startIdx += 1