题目描述找出数组中重复的数字。长度为n的数组nums中的所有数字都在0到n-1的范围内。数组中有些数字是重复的，但是不知道重复了多少个数字，也不知道每个数字重复了多少次。请找出数组中任何重复的数字。示例1：输入：[2,3,1,0,2,5,3]输出：2或3这道题的难度级别为Easy。idea1最直观的方式可能就是排序+遍历的方式。按照这个思路，很容易写出代码deffindRepeatNumber(nums:List[int])->int:ifnums==Noneorlen(nums)<2:returnnums.sort()foriinrange(1,len(nums)):#只要找到就可以返回ifnums[i]==nums[i-1]:returnnums[i]排序时间复杂度为$O(nlogn)$，时间遍历的复杂度为$O(n)$，即算法的时间复杂度为$O(nlogn)$，空间复杂度为$O(1)$。思路2使用字典作为计数器，只要字典中已经存在一个元素，就可以直接返回。按照这个思路，可以写成如下代码deffindRepeatNumber(nums:List[int])->int:ifnums==Noneorlen(nums)<2:returndicts={}foriinnums:#就可以了finditReturnifiindicts:returnidicts[i]=1与第一种算法相比，该算法以空间换取时间。因为只有一个循环，所以时间复杂度为$O(n)$，空间复杂度为$O(n)$。以上两种优化算法中的思路都比较容易想到，那么有没有不使用额外空间，时间复杂度为$O(n)$的算法呢？每当我们改变思路时，我们都需要重新思考这个话题，而不是纠结于现有的思维。如果数组nums不重复，则nums的索引集合等于nums中元素的集合（从集合的角度来看，不分先后）。即对于任何一个索引，都有一个唯一的元素与其相等且对应。但是如果nums包含重复的元素，那么对于一些索引，它会对应多个相同的元素，比如nums=[2,3,1,0,2,5,3]对应索引为2的数组中的两个2??，2个3在索引为3的对应数组中。我们可以将每个元素依次放入其对应的索引位置，如果该元素与对应索引位置的元素相等，则表示该元素重复。按照这个思路，可以写成如下代码deffindRepeatNumber(nums:List[int])->int:ifnums==Noneorlen(nums)<2:returnforiinrange(len(nums)):#索引与对应元素不一致，调整元素位置，直到索引与元素匹配或找到重复元素whilei!=nums[i]:#如果当前元素对应的索引位置的值为等于当前元素ifnums[i]==nums[nums[i]]:returnnums[i]#交换nums[i]的值和i的位置temp=nums[i]nums[i],nums[temp]=nums[temp],nums[i]上面的代码虽然包含了2个循环，但是每个位置可以结束的次数有限。因此，总的时间复杂度为$O(n)$，不需要额外的空间，空间复杂度为$O(1)$。总结了惨痛的教训后，我终于决定开始认真的做题了。之前的间歇期一直处于放弃的状态，导致我现在基本都是从零开始。我会尽量总结我做过的题目。由于本人对数据结构和算法了解有限，请勿喷。
