题目

• 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

本文题目：Find the Duplicate Number

代码详解

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i ++ ) {
            int index = abs(nums[i]) - 1;
            // 标记已访问
            nums[index] *= -1;
            
            if (nums[index] > 0)   // 访问到两次
                return abs(nums[i]);
        }
        return 0;
    }
};

用取负数来标记访问次数

• $Input: nums = [1,3,4,2,2]$

$$ \begin{align} & index\space =\space nums[0]\space -\space 1\space =\space 0;\\ & nums[0]\space =\space 1\space *\space (-1)\space =\space -1;\\ & index\space =\space nums[1]\space - \space 1\space =\space 2;\\ & nums[2]\space =\space 4\space *\space (-1)\space =\space -4;\\ & index\space =\space nums[2]\space -\space 1\space =\space 3;\\ & nums[3]\space =\space 2\space *\space (-1)\space =\space -2;\\ & index\space =\space nums[3]\space -\space 1\space =\space 1;\\ & nums[1]\space =\space 3\space *\space (-1) \space =\space -3;\\ & index\space =\space nums[4]\space -\space 1\space =\space 1;\\ & nums[1]\space =\space -3\space *\space (-1)\space =\space 3\space >\space 0;\\ & return\space nums[4]\space // 返回 2 \end{align} $$

• 至此，不难看出，由于重复出现的数只有一个，即整数$\space [1,\space n]\space $中有$\space n-2 \space $个都是唯一的，他们与其$\space nums[index] \space$都是一一对应，只有重复的数两次取反之后为正数