442_数组中重复的数据

类型：数组

• 442. 数组中重复的数据 💛

  https://leetcode-cn.com/problems/find-all-duplicates-in-an-array/

  ❓ 给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。找到所有出现两次的元素。

  💡 原地哈希

  通过取相反数的形式，既保留了原来元素的信息(绝对值不变)，同时还可以标记变化（第nums[i]个元素小于0说明之前出现过nums[i]）。

  def findDuplicates(nums):
      if not nums: return []
      res=[]
      n = len(nums)
      # 1<=num<=n 遍历到 num 则令第 num 个元素变成-num
      for i in range(n):
          num=abs(nums[i])
          # 如果第num个数字已经是负的 说明之前遇到过num 说明num出现两次
          if nums[num-1]<0:
              res.append(num)
          else:
              nums[num-1]=-nums[num-1]
      return res

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