[LeetCode] twoSum (with Python)

문제링크

https://leetcode.com/problems/two-sum/description/

Two Sum - LeetCode

문제설명

num배열과 target이 주어지고

num배열 안에 있는 정수 중 두개의 합이 target이 되는 두 정수값의 인덱스를 출력하라고 한다.

 

문제풀이

브루트 포스를 활용하여 O(N^2) 시간복잡도로 풀수도 있지만

나는 투포인터를 사용하여 O(N)만에 풀었다. 정렬도 사용했으니 최종코드의 시간복잡도는 O(NlongN) 이겠다.

그리고 solution에는 해시테이블을 사용하여 푼 풀이도 있었다.

 

투포인터로 코드 구현할때

인덱스와 값을 묶어 튜플로 저장하는 과정에서 나는 직접 반복문을 돌려 추가하였다.

# for i in range(N):
    # arr.append((nums[i], i))  #(2, 0), (7, 1), (11, 2), (15, 3)

 

코드

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        N = len(nums)
        i, j = 0, N-1

        copyNums = sorted(enumerate(nums), key = lambda x: x[1])
        
        while i < j:
            sumValue = copyNums[i][1] + copyNums[j][1]
            if sumValue < target:
                i += 1
            elif sumValue > target:
                j -= 1
            else:
                return [copyNums[i][0], copyNums[j][0]]