[LeetCode > Easy > 1] Two Sum

문제

• https://leetcode.com/problems/two-sum/description/
• Runtime: 59ms, Memory 17.99MB
• 주어진 배열에서 합쳐서 target 값이 되는 두 개의 값을 찾는다. (두 개의 값이 아닌 인덱스를 반환)

내 풀이

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
    	# 주어진 리스트의 index, value가 담긴 리스트 생성
        pointers = list(enumerate(nums))
        # value를 기준으로 리스트 정렬
        pointers.sort(key=lambda x: x[1])

        size = len(nums)
        # 투포인터로 풀이
        x, y = 0, size-1
        while pointers[x][1] + pointers[y][1] != target:
            if pointers[x][1] + pointers[y][1] > target:
                y -= 1
            elif pointers[x][1] + pointers[y][1] < target:
                x += 1
                
        return [pointers[x][0], pointers[y][0]]

• 시간 복잡도
  • nums의 길이가 n이라고 가정, O(nlogn)
  • 2 <= n <= 10⁴
  • ( enumerate로 n ) +  ( sort nlogn ) + ( 투포인터 n )

다른 풀이 방법

• 브루트포스 이중 반복문으로 2개씩 모두 비교
• 다른 값 찾기 리스트는 for로 반복하며, target - n의 값이 리스트 내에 있는지 확인
  • 리스트 내에 있는지 확인할 때, in 또는 value가 key이고 index가 value인 dictionary를 사용