167. Two Sum II - Input Array Is Sorted - 번외 알고리즘 코딩 인터뷰

167. Two Sum II - Input Array Is Sorted

1주차 - Array 배열 공부 [코딩 인터뷰 공부]

1주차 - 1.Two Sum LeetCode 리트코드 필수 문제 [코딩 인터뷰 공부]

이 문제는 1주차 Array 배열 공부 커리큘럼에 없는 번외 문제입니다.

 

오름차순의 array numbers 에서 두 elements의 합이 target이 될 때, 두 elements 의 index 를 오름차순으로 return 하시오.

 

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.

 

예시 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: 2 와 7 의 합이 9. 그러므로 index1 = 1, index2 = 2. Return [1, 2].


예시 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: 2 와 4 의 합이 6. 그러므로 index1 = 1, index2 = 3. Return [1, 3].


예시 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: -1 과 0 의 하빙 -1. 그러므로 index1 = 1, index2 = 2. Return [1, 2].

.

.

.

.

.

.

풀이

Dictionary

output = {}
        
for i,n in enumerate(numbers):           
    if n in output:
        return [output[n], i + 1]
    else:
        output[target - n] = i + 1

시간 복잡도: O(n)

공간 복잡도: O(n)

 

Two-Pointers

l, r = 0, len(numbers) - 1
        
while l < r:
    tsum = numbers[l] + numbers[r]
    if target == tsum:
        return [l + 1, r + 1]
    elif target < tsum:
        r -= 1
    else:
        l += 1

시간 복잡도: O(n)

공간 복잡도: O(1)