[LeetCode] Find the Duplicate Number

문제 링크 : https://leetcode.com/problems/find-the-duplicate-number/문제를 해결한 방법Map으로 확인하는 방법(시간복잡도 O(N), 공간 복잡도 O(N)) 정렬 후에, 이웃한 값을 비교하는 방법 (시간 복잡도 O(NlogN), 공간복잡도 O(1))플로이드의 거북이와 토끼 방법(투 포인터)The key insight in the algorithm is as follows. If there is a cycle, then, for any integers i ≥ μ and k ≥ 0, xi = xi + kλ, where λ is the length of the loop to be found and μ is the index of the first element of the cycle.

Based on this, it can then be shown that i = kλ ≥ μ for some k if and only if xi = x2i. ..........