Python LeetCode-442-数组中重复的数据（难度-

1.题目描述

给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）, 其中有些元素出现两次而其他元素出现一次。
找到所有出现两次的元素。你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？

示例
输入:
[4,3,2,7,8,2,3,1]
输出:
[2,3]

2.分析

这一题刚刚开始是很非常懵，主要是没有理解到"给定一个整数数组 a，其中1 ≤ a[i] ≤ n （n为数组长度）" 这个条件的真谛。 这个条件就是暗示我们可以使用这个数组里面的值帮我们来记录一些信息。

• 1.首先你的约束条件是 "你可以不用到任何额外空间并在O(n)时间复杂度内" ,所以不能两次遍历，只能遍历一次且需要用到数组里面的位置来帮助我们记录信息。
• 2.那么我们就考虑循环每个值，利用这个（值-1）代表的索引值来记录是否已经被遍历到。
• 3.遍历到则变为负数，如果第二次再次遍历到这个数，会发现这个数为负，则说明这个数是重复的。

3.解决

class Solution(object):
    
    def findDuplicates(self, nums):
        """
        主要的思路就是利用正负来保存第一次遍历到的数值的状态
        :type nums: List[int]
        :rtype: List[int]
        """
        res = []
        for i in range(len(nums)):
            index = nums[i] - 1  # 取到以这个值-1所在索引的值，判断这个值是否大于0
            if nums[index] > 0:  # 如果大于0，则说明这个值是第一次被遍历到，
                nums[index] = -nums[index]  # 则将这个值-1所在索引的值变负数，通过这个来记住已经遍历过一遍了
            else:  # 当这个值是负数，表示这个值第二次被遍历到了，所以它是重复的，故添加到res中即可
                res.append(nums[i])
        return res