442. 数组中重复的数据 中等 相关标签 相关企业 给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。 你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。 示例 1： 输入：nums = [4,3,2,7,8,2,3,1] 输出：[2,3] 示例 2： 输入：nums = [1,1,2] 输出：[1] 示例 3： 输入：nums = [1] 输出：[] 提示： n == nums.length 1 <= n <= 105 1 <= nums[i] <= n nums 中的每个元素出现 一次 或 两次

要解决这个问题，我们可以采用一种称为“原地哈希”的方法，这种方法允许我们在不使用额外空间的情况下，以 O(n) 的时间复杂度找出所有出现两次的整数。具体来说，我们可以利用数组 nums 本身作为一个哈希表，通过修改数组中的值来记录每个数字出现的次数。以下是解决这个问题的步骤：

1. 初始化：由于数组中的数字都在范围 [1, n] 内，我们可以假设 nums 数组的索引与数字是一一对应的。对于索引 i，如果 nums[i] 的值不等于 i+1，那么我们就知道 nums[i] 至少出现了一次。

2. 第一次遍历：遍历数组 nums，对于每个索引 i，如果 nums[i] 不等于 i+1，我们就将 nums[nums[i] - 1] 减一。这样，如果某个数字 x 出现了两次，那么 nums[x - 1] 将会是负数。

3. 第二次遍历：再次遍历数组 nums，这次我们收集所有 nums[i] 为负数的索引加一的值，因为这些就是出现两次的数字。

4. 返回结果：最后，我们将找到的所有出现两次的数字放入一个数组中并返回。

这种方法的时间复杂度是 O(n)，因为我们只遍历了数组两次，并且没有使用任何额外的空间，除了输入数组本身。

以下是这个问题的 Python 代码实现示例：

def findDuplicates(nums):
    # 初始化一个空列表来存储结果
    duplicates = []
    # 第一次遍历，将出现两次的数字对应的索引标记为负数
    for i in range(len(nums)):
        if nums[abs(nums[i]) - 1] < 0:
            duplicates.append(abs(nums[i]))
        else:
            nums[abs(nums[i]) - 1] *= -1
    # 返回出现两次的数字列表
    return duplicates

# 示例
print(findDuplicates([4,3,2,7,8,2,3,1]))  # 输出：[2, 3]
print(findDuplicates([1,1,2]))            # 输出：[1]
print(findDuplicates([1]))                # 输出：[]

请注意，这个解决方案是基于题目中给出的条件，即数组中的每个整数出现一次或两次，并且所有整数都在范围 [1, n] 内。579