287.寻找重复数

题解

题目：给一个数组，元素大小1~n,其中有一个数出现两次，要求用O(1)的空间复杂度求出这个出现两次的元素，并且不能修改原数组

思路：

快慢指针

1.快慢指针起始位置可以在0,0 也可以在0,1,总之fast总会和slow相遇，但是我比较喜欢写在0，0，不必纠结
2.可以将数组看作一个链表，比如[2,3,1,2],下标是[0,1,2,3]
3.则[0>2,1>3,2>1,3>2]---->2,1,3,2,1,3,2,1,3...
4.可以发现，这个链表是成环的，那么此题就变成了这一题
golang力扣leetcode 142.环形链表II
https://blog.csdn.net/qq_42956653/article/details/121689370
5.此题的入环点就是重复的数字，任何求入环点呢？
6.牢记：从相遇点到入环点的距离，恰好等于从链表头部到入环点的距离。

取巧

1.取出一个数，将其对应的下标上的数变号
2.如果遇到已经变号的数，说明之前被变号了，既然是1~n,说明现在遍历的这个数肯定是重复的
3.将原数组都回正
4.其实这种方法，感觉不满足“不能修改原数组”这个要求，擦边了，还是用第一种吧

代码

func findDuplicate(nums []int) int {
	fast, slow := 0, 0
	for {
		fast = nums[nums[fast]]
		slow = nums[slow]
		if fast == slow {
			fast = 0
			for fast != slow {
				fast = nums[fast]
				slow = nums[slow]
			}
			return slow
		}
	}
	return 0
}

func findDuplicate(nums []int) int {
	n := len(nums)
	ans := 0
	for i := 0; i < n; i++ {
		v := abs(nums[i])
		if nums[v-1] > 0 {
			nums[v-1] *= -1
		} else {
			ans = v
		}
	}
	for i := 0; i < n; i++ {
		if nums[i] < 0 {
			nums[i] *= -1
		}
	}
	return ans
}
func abs(i int) int {
	if i < 0 {
		return -i
	}
	return i
}