方法一原地交换

看到数组长度为n，数组内数据范围是1～n比较容易想到原地交换，把每个对应的数据排到”应该的位置”，比如我遇到了数字1，那么应该把他排到下标0的位置，遇到数字3应该排到下标2的位置。排好之后遍历一下数组，找到那些下标和数字不对应的数就是多出来的

参考代码

  1. class Solution:
  2.     def findDuplicates(self, nums: List[int]) -> List[int]:
  3.         for i in range(len(nums)):
  4.             while nums[nums[i] -1] != nums[i]:
  5.                 nums[nums[i] -1],nums[i] = nums[i],nums[nums[i] -1]
  6.         ans = []
  8.         for i in range(len(nums)):
  9.             if nums[i] != i + 1: 
  10.                 ans.append(nums[i])
  11.         return ans

复杂度分析

时间复杂度 O(n)
空间复杂度 O(1)

方法二标记

这道题要求我们用O(1)的空间复杂度来解决，因此我们直接利用他已经开辟好的空间进行标记。使用正负号来标记这个数出现没有，如果出现过就给他标记上负号，当第二次标记的时候就证明这个数出现过两次。

参考代码

  1. class Solution:
  2.     def findDuplicates(self, nums: List[int]) -> List[int]:
  3.         ans = []
  4.         for x in nums:
  5.             x = abs(x)
  6.             if nums[x - 1] > 0:
  7.                 nums[x - 1] = -nums[x - 1]
  8.             else:
  9.                 ans.append(x)
  10.         return ans

复杂度分析

时间复杂度 O(n
空间复杂度 O(1)