本文共 1102 字，大约阅读时间需要 3 分钟。

题目描述

给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。

假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。

示例 1：

输入：nums = [1,3,4,2,2]

输入：nums = [3,1,3,4,2]

输入：nums = [1,1]

输入：nums = [1,1,2]

解题思路

哈希表

public int findDuplicate_1(int[] nums) {           HashMap
   
     map = new HashMap<>();        for (int i = 0; i < nums.length; i++) {               if (!map.containsKey(nums[i])){                   map.put(nums[i],map.getOrDefault(nums[i],0)+ 1);            }else {                   return nums[i];            }        }        return -1;    }
   

快慢指针

//快慢指针    public int findDuplicate(int[] nums) {           int slow=0, fast=0;        int res=0;        while(true){               //寻找相遇点            slow=nums[slow];            fast=nums[nums[fast]];            //slow从相遇点走，fast从0开始，将相遇在入环点            if(slow==fast){                   fast=0;                while(fast!=slow){                       slow=nums[slow];                    fast=nums[fast];                }                res=fast;                break;            }        }        return res;    }

转载地址：http://bser.baihongyu.com/