2021-11-01：寻找重复数。给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数

2021-11-01：寻找重复数。给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数 ，找出 这个重复的数 。你设计的解决方案必须不修改数组 nums 且只用常量级 O(1) 的额外空间。力扣287。

答案2021-11-01：

方法1：快慢指针。
抽象为环形链表求入环节点。
方法2：位操作。此方法对于1到n都有的情况下适用。1到n，不是都有，不适合。

时间复杂度：O(N)。
额外空间复杂度：O(1)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {

    if true {

        nums := []int{1, 2, 3, 2, 4, 5, 6}

        ret := findDuplicate(nums)

        fmt.Println(ret)

    }

    if true {

        nums := []int{1, 2, 3, 2, 4, 5, 6}

        ret := findDuplicate2(nums)

        fmt.Println(ret)

    }

}

func findDuplicate(nums []int) int {

    if len(nums) < 2 {

        return -1

    }

    slow := nums[0]

    fast := nums[nums[0]]

    for slow != fast {

        slow = nums[slow]

        fast = nums[nums[fast]]

    }

    fast = 0

    for slow != fast {

        fast = nums[fast]

        slow = nums[slow]

    }

    return slow

}

func findDuplicate2(nums []int) int {

    if len(nums) < 2 {

        return -1

    }

    x1 := 0

    x2 := 0

    for i := 0; i < len(nums); i++ {

        x1 ^= i

        x2 ^= nums[i]

    }

    return x1 ^ x2

}

执行结果如下：

左神java代码

2021-11-01：寻找重复数。给定一个包含 n + 1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有 一个重复的整数的相关教程结束。