public int findDuplicate(int[] nums) {
int ret = 1;
for (int i=0;i<nums.length;i++){
if (nums[Math.abs(nums[i])]< 0){
ret = Math.abs(nums[i]);
break;
}else {
nums[Math.abs(nums[i])] *=1;
}
}
for (int i=0;i<nums.length;i++){
if (nums[i]<0){
nums[i] *=1;
}
}
return ret;
}
My easy understood solution with O(n) time and O(1) space without modifying the array. With clear explanation.



@echoxiaolee run time error when using input [10000000, 1, 1] slow = 10000000, and fast = nums[10000000], how can you guarantee slow and fast are always valid indexes?



The head of this list is 0, I think this one is easier to understand:
class Solution { public: int findDuplicate(vector<int>& nums) { if(nums.empty())return 0; int slow = 0,fast = 0; while(slow!=fastslow==0) { slow = nums[slow]; fast = nums[nums[fast]]; } slow = 0; while(slow!=fast) { slow = nums[slow]; fast = nums[fast]; } return fast; } };
Both the slow node and the fast node start from 0.