[1] Two Sum | Leetcode Easy

문제설명

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.

결과 예시

제한사항
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.


파이썬 코드

1번 풀이

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                if(nums[i] + nums[j] == target) :
                    return [i,j]

BruteForce방식으로 푼 코드입니다.
시간복잡도 - O(n^2)

2번 풀이

풀이코드를 참고했습니다. 해쉬맵을 사용하여 효율성이 훨씬 좋습니다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in hashmap:
                return [i, hashmap[complement]]
            hashmap[nums[i]] = i   

아래코드는 enumerate()함수를 활용한 코드입니다.

def twoSum(self, nums, target):
        seen = {}
        for i, v in enumerate(nums):
            remaining = target - v
            if remaining in seen:
                return [seen[remaining], i]
            seen[v] = i
        return []

시간복잡도 - O(n)


enumerate()

처음보는 함수이기에 정리해봅니다.

파이썬에서 for루프는 기본적으로

for <원소> in <목록>:

형태로 사용됩니다.

<목록>부분은 리스트(list), 튜플(tuple), 문자열(string), 반복자(iterator), 제너레이터(generator) 등 순회가 가능한 데이터 타입을 사용할 수 있습니다.
<원소>부분은 순회 변수(loop variable)라고 하는데, <목록>객체에 담겨진 원소들이 루프가 도는 동안 하나씩 차례로 <원소>에 할당됩니다.


enumerate()의 역할이 인덱스(index)와 원소값을 동시에 접근할 수 있게 해줍니다.

기본포맷

for <인덱스,원소> in enumerate(<목록>) :

예제

for i, value in enumerate(['A', 'B', 'C']):
	print(i, value)

#출력 결과
0, A
1, B
2, C

시작 인덱스를 바꾸고 싶은 경우

enumerate(<목록>, start = <숫자>)	#시작인덱스가 0부터가 아니라 <숫자>부터 시작

좋은 웹페이지 즐겨찾기