leet code 167 - Two Sum II - Input Array is Sorted

리트 코드의 첫문제인 two sum 과 거의 같은 문제.. 뭐가 다른거지?

 

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

해쉬맵으로 풀 수 있다. 왜 해쉬 맵을 쓰는가? 

 

문제는 간단하다. 배열을 전부 순회하며 타겟값을 만드는 조합을 찾는 브루트 포스의 방법이 있다.

 

하지만 이는 N2의 시간 복잡도를 지닐뿐더러 매우 비효율적이다. 

 

시간을 줄이려면 어떻게 해야할까? [1,2,3,4,5] target = 4을 봐보자.

첫번째 1을 골랐다면  탐색해야할건 배열 전부가 아니라  3 하나이다. 탐색을 위해 배열 을 전부 도는게 비효율 적이다.

 

해쉬맵을 사용하면 시간을 획기적으로 줄일 수 있다. 하지만 굳이 처음부터 해쉬맵을 이니셜라이징 할 필요는 없다. 

한번의 순회로 풀수 있는 풀이가 존재. 2가 존재하지 않기 때문에 2와 함께 인덱스 값을 저장하고, 3이 존재하지 않기 때문에 1과 함꼐 인덱스 값을 저장, 3에서는 1이 존재하기 때문에 1의 인덱스와 3의 인덱스를 반환한다. 다만 인덱스에서 +1 해서 반환.

 

---

추가적 공간을 사용하지 않는 풀이.

포인터 활용

 

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        

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

 2345811  target  9 라고 해보자.

 

초기 포인터 상황에선 2+ 11 타겟을 오버했기 때문에 값을 줄여야한다. 오른쪽 포인터 1칸 왼쪽으로 이동.

다음 2+ 8 타겟 오버. 오른쪽 포인터 한칸 왼쪽 이동.

2+ 5 타겟에 모자란다. 왼쪽 포인터 오른쪽으로 이동.

3 + 5 타겟 모자람. 왼쪽 포인터 오른쪽이동.

4+ 5 타겟 확정.

 

추가 메모리를 사용하지 않고 포인터를 사용해 타겟을 찾는 linear시간의 알고리즘이다.