68. Two Sum II - Input array is sorted

- 파이썬 알고리즘 인터뷰 68번 문제

2020.03.01

3 try

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

0. 이미 정렬된 배열이므로 투 포인터를 사용할 수 있다. 
1. left는 0에서, right는 len(numbers)-1 에서 시작한다.
2. cal_sum은 left, right가 위치하고 있는 값의 합이다.
3-1. cal_sum이 target보다 크면...
값을 줄여줘야 되니까 right -= 1
3-2. cal_sum이 target보다 작으면...
값을 키워야 되니까 left += 1
3-3. cal_sum == target이면...
return (left + 1, right + 1)	# 문제에서 1에서부터 시작하는 인덱스라고 했다~

-

-

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for idx, cur_num in enumerate(numbers):
            expected = target - cur_num
            left, right = idx + 1, len(numbers) - 1
            while left <= right:
                mid = left + (right - left) // 2
                if numbers[mid] < expected:
                    left = mid + 1
                elif numbers[mid] > expected:
                    right = mid - 1
                else:
                    return idx + 1, mid + 1

- 첫번째 숫자는 for문으로 앞에서부터 차례대로 접근하고,
첫번째 숫자에 두번째 숫자를 더했을 때 target이 되어야 하므로 두번째 숫자는
>> expected = target - (cur_num) 이되어야 한다.
- 그리고 두번째 숫자(expected)가 나머지 범위 안에 있는지를 이진 검색으로 판별한다.

import bisect

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for idx, cur_num in enumerate(numbers):
            expected = target - cur_num
            i = bisect.bisect_left(numbers, expected, idx + 1) 	# 현재 cur_num의 [idx+1~끝] 범위에 target이 있는지 검사
            if i < len(numbers) and numbers[i] == expected:	# 만약 target이 존재하면
                return idx + 1, i + 1

- 첫번째 숫자는 for문으로 앞에서부터 차례대로 접근하고,
첫번째 숫자에 두번째 숫자를 더했을 때 target이 되어야 하므로 두번째 숫자는
>> expected = target - (cur_num) 이되어야 한다.
- 그리고 두번째 숫자(expected)가 나머지 범위 안에 있는지를 이진 검색으로 판별한다.

- bisect_left(a, x, lo = 0, hi = len(a))
1. lo는 왼쪽 범위를 제한한다.
2. hi는 오른쪽 범위를 제한한다.