[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부터가 아니라 <숫자>부터 시작
Author And Source
이 문제에 관하여([1] Two Sum | Leetcode Easy), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yoongyum/1-Two-Sum-Leetcode-Easy저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)