while (nums[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]);

这行代码使得数组

位置0， 放置数字0，…

位置n-1，放置数字n-1

i=0

nums[0]=4，因为 nums[4] != nums[0] ，数字 4 不在正确位置。

swap(nums[0], nums[nums[0]]) ， nums[0]=4 ， 把数字4放在正确的位置，数轴上4的位置。

nums[0]=1，因为 nums[1] != nums[0] ，数字 1 不在正确位置。

swap(nums[0], nums[nums[0]]) ， nums[0]=1 ， 把数字1放在正确的位置，数轴上1的位置。

…

依次类推

不断的使，nums[i]交换到正确的位置，直到遇到“ nums[i](值记录为a)在正确位置，但是另一个a(位置记录为j,j!=i)”出现， 两个不同位置上的数相等。这种情况，nums[i]就是需要寻找的，重复的数字。

class Solution {
public:
    int duplicateInArray(vector<int>& nums) {
        int n = nums.size();
        // 先去除不在0~n-1范围的数，防止下标越界
        for (auto x : nums)
            if (x < 0 || x >= n)
                return -1;
        for (int i = 0; i < n; i ++ ) {
            // 如果没有重复元素，经过这一步操作，0位置将会存储0， i位置将会存储i
            while (nums[nums[i]] != nums[i]) swap(nums[i], nums[nums[i]]);
            // 如果有重复元素 将会导致 因为有两个相同的数 但是只有一个位置 所以位置和值不能一一对应
            if (nums[i] != i) return nums[i];
        }
        // 找不到重复的数就返回-1 
        return -1;
    }
};

时间复杂度 $O(n)$

空间复杂度 $O(1)$