题目

给你一个长度为 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 <= 10^5
1 <= nums[i] <= n
nums 中的每个元素出现 一次 或 两次
来源：力扣（LeetCode）

解题思路

  这是一个经典的鸽笼原理题，一个萝卜一个坑，如果坑已经被填上了，就能发现谁是重复的了。以示例1为例，我们想办法在原数据不丢失的情况下还能表示当前坑位是否被占用。题目给定了数组中的数字是【1,n】这也就预示着可以利用数字的正负来标记坑位是否被占用的信息，举例：第一个元素4那么第四个位置的7变成-7即可，这样7的信息也不会丢失，当我们遍历到7那里，直接取绝对值就能还原出它真实的数值。-7表示第四个坑位已经被占用，这样在遍历的过程中就能轻松发现被占的坑。

class Solution:def findDuplicates(self, nums: List[int]) -> List[int]:temp=[]for i in range(len(nums)):if nums[abs(nums[i])-1]>0:nums[abs(nums[i])-1]=-nums[abs(nums[i])-1]else:temp.append(abs(nums[i]))print(nums)return temp