一、题干：数组中重复的数据

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。
你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

示例 1：
输入：nums = [4,3,2,7,8,2,3,1] 输出：[2,3]
示例 2：
输入：nums = [1,1,2] 输出：[1]
示例 3：
输入：nums = [1] 输出：[]

提示：

• n == nums.length
• 1 <= n <= 105
• 1 <= nums[i] <= n

• nums 中的每个元素出现 一次 或 两次

  二、解题思路：

  1. 初版：

  题目要求时间复杂度O(n)，额外空间复杂度O(1)，我的第一反应是：使用hashmap常数级的查找特性，故立马写出了：

  //时间复杂度：O(n)
  //额外空间复杂度：O(n)
  func findDuplicates(nums []int) []int {
    hash:=make(map[int]bool)
    var res []int
    for _,num:=range nums{
        if hash[num]==false{
            hash[num]=true
        }else{
            res=append(res,num)
        }
    }
    return res
  }

  提交结果如下图所示，本来自以为时间应该挺快的，没想到排倒数，哈哈哈，看来相比于其他题解，hash查找还是较费时的。
  

  2. 改进：

  因为元素范围1-n，故可将元素作为下标，利用已给定的数组空间，进行标记;而采取的标记方式应该使得该位置上的元素可以被还原，故通过+n的方式来标记，通过%n的方式来还原。
  判断标准：全部标记后，若元素大于2n，则下标i+1即重复出现过两次

  //时间复杂度：O(n)
  //额外空间复杂度：O(1)
  func findDuplicates(nums []int) []int {
    n:=len(nums)
    var res []int
    for _,num:=range nums{
        x:=(num-1)%n
        nums[x]+=n
    }
  
    for i,num:=range nums{
        if(num>(n<<1)){
            res=append(res,i+1)
        }
    }
    return res
  }
  

  提交结果如下图所示，果然这样更简单直接一点！