题目

难度：★★☆☆☆
类型：数组
方法：哈希表

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

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

找到所有出现两次的元素。

你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗？

示例：

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

输出:
[2,3]

解答

我们使用O(n)的时间复杂度和O(1)的空间复杂度来解决这个问题。

思路：注意题目给定的条件，1 ≤ a[i] ≤ n，数组中每一个元素是满足上界和下界条件的。我们可以这样考虑，遍历数组中每一个元素，以该元素的数值作为下标索引，将该索引对应的数组中的元素取相反数，对于数组中重复的元素，则第二次遍历到该元素时，以该元素为索引在数组中对应的元素一定是负数，添加到结果即可。

需要注意，这里每个元素的范围是1到n，我们需要通过减一变换到不会使数组溢出的范围0到n-1，另外，由于遍历过程中可能存在负数，我们取索引时需要考虑到这一情况，取其相反数。

class Solution:
    def findDuplicates(self, nums):
        if not nums:
            return []

        res = []
        index = 0
        while index < len(nums):
            num = nums[index]
            point = abs(num) - 1
            if nums[point] < 0:
                res.append(abs(num))
            nums[point] = -nums[point]
            index += 1
        return res

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析