[LeetCode] 287. Find the Duplicate Number

Problem

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

Constraints:

• 1 <= n <= 10^5
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.

---

Solution

class Solution {
    public int findDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++)
            if (!set.add(nums[i])) return nums[i];
        return 0;
    }
}

Explanation

• 배열 내에서 중복된 값을 찾기 위해 자료구조 Set을 선언하고, Set에 이미 저장된 값을 다시 저장하려하면 해당 값을 반환하도록 한다.

  Set<Integer> set = new HashSet<>();
  for (int i = 0; i < nums.length; i++)
    if (!set.add(nums[i])) return nums[i];
  return 0;