💻 [LeetCode] Contains Duplicate - 217

지난 릿코드 포스트에 해쉬맵을 사용한 Majority Element 문제들을 풀어봤는데, 이번 문제도 거의 비슷한 알고리즘으로 코드를 짤 수 있어서 짧게 짚고 넘어가보겠다! 😚

---

👩🏻‍💻 217. Contains Duplicate

"Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct."

내가 생각한 알고리즘:

• empty 해쉬테이블을 만들고, array nums 를 loop을 돌렸을 때,
• 우리가 찾는 key 값이 해쉬테이블 안에 있으면 True 리턴
• 해쉬테이블 안에 없으면 해쉬테이블의 key값을 element로, value값을 index로 추가
• loop을 벗어났을 때, False 리턴 (룹 내에서 아무것도 리턴하지 않았다는 건 모든 element들이 distinct 하다는 뜻)

👊🏻 코드를 적어보자!

def containsDuplicate(nums: List[int]) -> bool:
	
    hashTable = {}
    for idx, val in enumerate(nums):
    	if val in hashTable:	# there are duplicates
        	return True
        else:
        	hashTable[val] = idx	# adding into hashTable
    return False

쉬운 코드다!
그냥 brute force 로는 Time complexity가 O(n^2) 가 나올텐데 해쉬맵을 쓰면 비교적 빠르게 O(n) 의 시간복잡도를 가질 수 있다 🤓

---

📍 정리

이 문제도 해쉬테이블..
물론 다른 approach로 알고리즘을 짤 수도 있겠지만, 나는 지금 인터뷰를 준비하기 때문에..ㅠㅠ 적당히 해쉬맵을 써서 빨리빨리 다음 문제로 넘어가야 하는 현실 😥