442. 数组中重复的数据

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

解法一：O（lgn）

借鉴26. 删除排序数组中的重复项

先排序，然后一次遍历 O（lgn） + O（n）

解法二：O（n）

由于数字范围与数组长度有关(1 ≤ a[i] ≤ n ),因此可以将元素值与元素下标联系起来(由于下标范围是0~n-1,因此还需要做一个偏移)。

遍历数组，将元素值作为下标(index)，用index访问数组，每次访问就将该元素置反（添负号），这样第二次访问为负的元素就是 重复项。

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        res = []
        for i in range(len(nums)):
            index = abs(nums[i]) - 1    #数组元素值映射为下标
            if nums[index] < 0:     #第二次访问
                res.append(index+1)            
            nums[index] = -nums[index]  #每次置反
        return res