给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
示例 1:
输入: [1,3,4,2,2] 输出: 2 示例 2:
输入: [3,1,3,4,2] 输出: 3 说明：
不能更改原数组（假设数组是只读的）。 只能使用额外的 O(1) 的空间。 时间复杂度小于 O(n2) 。 数组中只有一个重复的数字，但它可能不止重复出现一次。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/find-the-duplicate-number 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 贴一下大佬的解释：
https://leetcode-cn.com/problems/find-the-duplicate-number/solution/kuai-man-zhi-zhen-de-jie-shi-cong-damien_undoxie-d/
class Solution { public: int findDuplicate(vector<int>& nums) { int slow = 1, fast = 1; do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast); int finder = 1; do { finder = nums[finder]; slow = nums[slow]; } while(slow != finder); return finder; } };思路：将数组看成是一个特殊的链表，数组的下标就是数组元素的地址。每一个元素看成一个含有指针的节点。如果数组有重复元素，抽象成链表说明一个节点有两个指针指向它，就能够变成一个环。入环处即为重复元素。
最初个人不是很理解为什么下标不能从1开始。 经过实验，发现如果从下标1建立链表，如果环不在1处闭合，则没问题。若把0 3 1 2 4 3看成链表，3 1 2 4 3成环，如果从0开始，那么3为入环处，并且为重复元素。但是从1开始，环就变成了1 2 4 3 1，1变成了入环处，答案错误。 想了一下终于想明白了。自己的本意是不从0节点开始，因为0不可能作为入环处，而且也可以不看做链表的元素，仅仅当成头节点。打算从0节点的下一个节点“1”开始。很明显0节点的下一个节点不是1节点，应该是从nums[0]开始。惯性思维真的恐怖，根本没发现这个错误。（根本原因应该是没完全理解这个题） 提交上去答案依然错误。当nums[0]作为入环处时，答案就会出现错误。经过检查，发现是不能写成do while循环。
class Solution { public: int findDuplicate(vector<int>& nums) { int slow = nums[0], fast = nums[0]; do { slow = nums[slow]; fast = nums[nums[fast]]; } while (slow != fast); int finder = nums[0]; while(slow != finder) { finder = nums[finder]; slow = nums[slow]; } return finder; } };又思考了一下，为什么不能从其他节点开始？数组n个元素，我任取其中一个节点开始不行吗？重点是“入环处”。先把数组抽象成链表，再重点求链表的入环处，就是本题的思路。把思路转到求链表的入环处上，如果没有0这个头节点，那么这个题还能做吗？0节点的存在使得整个链表不可能为环，即一定有入环处。如果从0节点或者nums[0]节点以外的节点开始，如果该节点恰好位于环中，那么这个节点就成为了不是入环点的“入环点”。
思考太深了，简便一下。快慢指针的模板题141 142都是要求从头节点head开始的，所以套用模型，数组抽象成的链表也要从头节点开始。问题又回到了其他节点为什么不能作为头节点？为什么必须从头节点开始？因为我们要找的是整个链表的入环处，因此必须从头节点开始，遍历整个链表。而如果从其他节点开始，就不能成功遍历整个链表。
为什么建立整个链表，不能从除0、nums[0]的其他节点开始？ 因为一定没有指向0的节点，0一定是头节点，因为数组的特殊性，其他元素一定有非0下标，即其他节点一定有指向它的父节点，不可能作为头节点 问题总算解决了，累死了。萌新第一次接触快慢指针问题，前半段根本没理解就想了一堆不该想的，还是太菜了。
