方法一：哈希表法（时间复杂度 O(n)，空间复杂度 O(n)）

核心思想

利用 HashSet 的去重特性，遍历数组时若元素已存在于集合中，则为重复数字。

代码示例

public int findDuplicate(int[] nums) {
    if (nums == null || nums.length == 0) return -1;
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        if (num < 0 || num >= nums.length) return -1; // 输入合法性检查
        if (!set.add(num)) return num;
    }
    return -1;
}

优缺点

• 优点：逻辑简单，适合任意范围的数组。
• 缺点：需要额外 O(n) 空间 。

方法二：排序法（时间复杂度 O(n log n)，空间复杂度 O(1)）

核心思想

先排序数组，重复元素必相邻。遍历时比较相邻元素即可。

代码示例

public int findDuplicate(int[] nums) {
    if (nums == null || nums.length == 0) return -1;
    Arrays.sort(nums);
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] == nums[i-1]) return nums[i];
    }
    return -1;
}

适用场景

• 允许修改原数组且对空间复杂度敏感的场景