[Python][LeetCode] Two Sum II (두 수의 합)

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/

Two Sum II - Input Array Is Sorted - LeetCode

문제 설명:

리스트가 주어졌을때 타겟의 값이 나오도록 두 수를 찾는 문제다

이 때 반환값은 찾은 두 수의 인덱스 번호이다.

 

투 포인터

• left는 가장 앞에 right는 리스트의 가장 뒤에 배치한다.
• 만약 리스트[left] 리스트[right]의 값이 같으면 인덱스를 반환하고
• 더한 값이 크다면 right의 인덱스 번호를 줄여준다.
• 더한 값이 타겟보다 작으면 left의 인덱스 번호를 큰쪽으로 옮겨준다.

        left, right = 0, len(numbers)-1
        while not left == right:
            if numbers[left] + numbers[right] < target:
                left += 1
            elif numbers[left] + numbers[right] > target:
                right -= 1
            else:
                return [left+1,right+1]

 

이진탐색

• 위의 방식과 비슷하나
• mid 값을 둠

        for k, v in enumerate(numbers):
            left, right = k+1, len(numbers)-1
            expected = target-v
            print(expected)
            while left <= right:
                mid = left + (right-left) // 2
                if numbers[mid] < expected:
                    left = mid+1
                elif numbers[mid] > expected:
                    right = mid-1
                else:
                    return k+1, mid+1