287: Find the Duplicate Number

Link : https://leetcode.com/problems/find-the-duplicate-number/solution/

---

1. 문제

• Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.You must solve the problem without modifying the array nums and uses only constant extra space.
  There is only one repeated number in nums, return this repeated number.

 

---

2. 문제의 조건

• 1 <= n <= 10^5
• nums.length == n + 1
• 1 <= n ums[i] <= n

 

---

3. 문제 접근

• 아이디어
  
  해당 방식은 "중복"여부만 판단하면 되므로 저는 시간복잡도와 공간복잡도가 모두 O(N)인 시점으로 해결하였습니다.
  HashMap, Dictonary를 이용하면 간단합니다.

 

---

4. 풀이 방법

• 만약 val가 dict에 포함되어 있다면? = 이미 나온값
• 만약 val가 dict에 포함되어있지 않다면? = 처음나온값
• 이 두개를 이용하여 이미 나온 값의 경우 바로 return해주시면 됩니다.

 

---

5. 소스코드

• https://cjw-git.tistory.com/182

 

---

 

cjw.git@gmail.com