LeetCode Two Sum(Python)

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

Two Sum - LeetCode

 

 

문제접근

• 주어진 리스트 중에 두 원소를 합해서 target과 같은 두 원소의 index를 return하는 문제
• 일반적으로 생각하면 이중 for문을 이용하여 완전탐색해주면 되겠으나 문제 제한이 nums.length<=10^4이므로 O(n^2)의 시간복잡도를 사용하면 시간초과가 날 수 있음(O(n)만에 풀어야 함)

 

아이디어

• 주어진 리스트(nums)를 탐색하여 target-nums[i]가 리스트에 존재하는지를 파악하면 됨
•  주어진 리스트를 딕셔너리(해시테이블)에 담고 target-nums[i]가 딕셔너리에 존재하는지를 파악함
• 시간 복잡도를 줄이기 위해 딕셔너리를 사용해 전체 탐색시간을 줄임
• in을 활용하여 전체 탐색 딕셔너리 : O(1), 리스트(배열) : O(n) 대신 딕셔너리는 메모리를 더 사용

 

정답 코드

class Solution:
    def twoSum(self, nums, target):
        memo = {}

        for index, v in enumerate(nums):
            memo[v] = index
        for index, v in enumerate(nums):
            needed_number = target - v
            # memo와 nums를 비교하여 같은 수가 사용되는 상황 제거
            if needed_number in memo and index != memo[needed_number]:
                return [index, memo[needed_number]]

정렬을 이용하거나하는 다른 풀이로도 풀 수 있는지 다시 풀어볼 예정