📃 题目描述

题目链接：剑指 Offer 03. 数组中重复的数字 (opens new window)

🔔 解题思路

利用数据结构特点，容易想到使用哈希表（Set）记录数组的各个数字，当查找到重复数字则直接返回，这里就不贴代码了

题目说明在一个长度为 n 的数组 nums 里的所有数字都在 0 ~ n-1 的范围内 。 此说明含义：数组元素的 索引 和 值 是 一对多 的关系。

因此，可遍历数组并通过交换操作，使元素的 索引 与 值 一一对应（即 nums[i] = inums[i]=i ）。因而，就能通过索引映射对应的值，起到与字典等价的作用。

class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            int targetIndex = nums[i];
            // 当前 nums[i] 出现在正确的位置
            if (targetIndex == i) {
                i ++;
            } 
            else if (nums[targetIndex] != nums[i]) {
                swap(nums, i, targetIndex);
            } 
            // nums[targetIndex] == nums[i], 重复数字
            else {
                return nums[i];
            }
        }

        return -1;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：