力扣随笔之寻找重复数（中等287）

本文主要是介绍力扣随笔之寻找重复数（中等287），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路1：暴力解法，根据要求不修改数组且只用常量级O(1)的额外空间，我们写两层嵌套循环，寻找重复的数;可以解决部分问题，但会超出时间限制无论Java还是C++;

Java实现：

class Solution {public int findDuplicate(int[] nums) {for(int i = 0;i < nums.length - 1;i++){for(int j = i+1;j < nums.length;j++){if(nums[i] == nums[j]){return nums[i];}}}return -1;}
}

思路2：根据快慢指针来解决，由于nums数组中有且仅有一个重复的整数，那么可以将nums数组链表化，因为有“一个”重复的整数，所会有有且仅有“一个环”产生，根据快慢指针找到环的入口，即可 

        如图slow一次走一步，fast一次走两步，得到如下数学关系

定义指针p1 从slow开始走，p2从0开始走，当p2与p1相遇，相遇那个点就是环的入口

Java实现：

class Solution {public int findDuplicate(int[] nums) {int slow = 0;int fast = 0;slow = nums[slow];//slow一次走一步fast = nums[nums[fast]];//fast一次走两步while(slow != fast){//当slow没遇到fastslow = nums[slow];fast = nums[nums[fast]];}//slow遇到fastint p1 = slow;int p2 = 0;while(p1 != p2){p1 = nums[p1];p2 = nums[p2];}return p1;//最后return p1或者p2皆可}
}

这篇关于力扣随笔之寻找重复数（中等287）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---