[LeetCode] 1. Two Sum

date

Oct 11, 2024

slug

leetcode-1

author

status

Public

문제 링크

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

문제

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

문제풀이

Solution 1

Full Linear Search로 의 시간 복잡도를 가지게 풀 수 있다.

idx 2개를 돌면서 값이 일치하는 2개의 idx를 리턴

Solution 2

Dictionary를 사용해 로 한번의 Linear Search로 풀 수 있다.

순회할 때 마다 Target - num의 값을 dict에서 찾아서 있으면 그대로 Idx 2개 리턴

없으면 현재 {key: value} = {num, idx}를 Dict로 넣는다.

문제에서는 항상 정답이 있으니 없을때는 고려하지 않아도된다.

파이썬 문제풀이 코드


from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        # Solution 1 
        # Time Complexity O(n^2)
        # for i in range(len(nums)):
        #     for j in range(i+1, len(nums)):
        #         if nums[i] + nums[j] == target:
        #             return [i, j]
        
        # Solution 2
        # Time Complexity O(n)
        num_element_dict = dict()
        for idx, num in enumerate(nums):
            if num_element_dict.get(target - num, -1) >= 0:
                return [idx, num_element_dict[target-num]]
            else:    
                num_element_dict[num] = idx            
                
s = Solution()         
print(s.twoSum(nums=[2,7,11,15], target=9))

시간복잡도

입력

2 <= nums.length <= 10^4

10^9 <= nums[i] <= 10^9

10^9 <= target <= 10^9

출력

예제 입력


nums = [2,7,11,15], target = 9

예제 출력


[0, 1]


nums = [3,2,4], target = 6


[1, 2]

알고리즘 분류

구현