[LeetCode] Two Sum II

목차

문제

• numbers에서 두 개의 값을 뽑았을 때 target값이 되는 index1과 index2를 찾는 문제입니다.
• 예시

  • Input: numbers = [2,7,11,15], target = 9
    Output: [1,2]
    Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

  • Input: numbers = [2,3,4], target = 6
    Output: [1,3]
    Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

  • Input: numbers = [-1,0], target = -1
    Output: [1,2]
    Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

• 제약조건
  • 2 <= numbers.length <= 3 * 104
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in non-decreasing order.
  • -1000 <= target <= 1000
  • The tests are generated such that there is exactly one solution.

문제 풀이

풀이 1 : Two Pointers

• 풀이
  • 투포인터의 전형적인 문제입니다. 정렬되어져 있는 리스트가 있을 때 left, right = 0, len(numbers)-1에서 시작해서 둘의 합이 target보다 크다면 right를 감소시켜 둘의 합을 줄여주고, target보다 작다면 left를 증가시켜 둘의 합을 키워주는 방식으로 값을 찾아나갑니다.
  • left에서 오른쪽으로 이동하면 정렬되어져 있기 때문에 무조건 더해지는 값이 커지게 될 것입니다. 반대로 right에서 왼쪽으로 이동하면 무조건 더해지는 값이 작아지게 될 것입니다. 이러한 방식으로 합이 target과 일치하는 지점을 찾아나가면 됩니다.
• 코드

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

• 시간복잡도
  • O(n)

알게 된 내용

• 투 포인터

출처

• https://leetcode.com/explore/learn/card/array-and-string/203/introduction-to-string/1162/