leetcode刷题 Day10

题目：

思路：利用Set的无重复值特性，找出重复值即可
代码：

class Solution {
    public int findDuplicate(int[] nums) {
        int checkNum=0;
        Set set=new HashSet();
        for(int i=0;i<nums.length;i++){
            if(!set.add(nums[i])){
                checkNum=nums[i];
            }
        }
        return checkNum;
        
    }
}

运行结果：

PS：此题要求空间复杂度为O(1)，代表不能开辟新的hashset或者新的数组进行解题，数组只读，所以也不能对数组进行排序。所以需要换个方法，采用双指针的办法，定义快指针（fast）和慢指针(slow)，快指针每次走两步(fast=nums[nums[fast])，慢指针每次走一步(slow=nums[slow])，当两个指针相等时，说明有循环，将fast变为与slow步子一致，循环当两指针相等时，就是循环入口，返回该入口即可。

class Solution {
    public int findDuplicate(int[] nums) {
        int fast=0;
        int slow=0;
        if(nums.length>1){
            while(true){
                fast=nums[nums[fast]];
                slow=nums[slow];
                if(slow==fast){
                    fast=0;
                    while(nums[fast]!=nums[slow]){
                        fast=nums[fast];
                        slow=nums[slow];
                    }
                    return nums[fast];
                }
            } 
        }
        return -1;
    }
}

运行结果：