难度: Medium
给你一个长度为 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.length1 <= n <= 1051 <= nums[i] <= nnums 中的每个元素出现 一次 或 两次运行时间: 41 ms
内存: 23.9 MB
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
if not nums:
return []
ans = []
for num in nums:
idx = abs(num) - 1
val = nums[idx]
if val < 0:
ans.append(abs(num))
nums[idx] = -nums[idx]
return ans
该题解采用了一个巧妙的方法来在原地标记数组中已经访问过的数字，利用数组元素的符号进行标记。具体步骤如下： 1. 遍历数组中的每一个元素。 2. 使用当前元素的绝对值减一得到数组的索引位置 `idx`。 3. 检查位于 `idx` 的元素的符号。 - 如果该位置的元素为负数，说明之前已经访问过该位置，因此当前数字是重复的，将其加入结果列表。 - 如果该位置的元素为正数，将其变为负数，表示该位置已被访问过。 4. 遍历完成后，结果列表中的元素即为出现两次的数字。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
if not nums: # 如果数组为空，直接返回空列表
return []
ans = [] # 初始化结果列表
for num in nums: # 遍历数组中的每一个数字
idx = abs(num) - 1 # 计算索引位置
val = nums[idx] # 获取该位置上的值
if val < 0: # 如果该位置上的值为负，说明之前已经访问过，当前数字是重复的
ans.append(abs(num)) # 将该数字添加到结果列表中
nums[idx] = -nums[idx] # 将该位置的值取反，标记为已访问
return ans # 返回结果列表
此算法无法区分一个数字出现两次还是多于两次。算法设计仅能检测到某个数字是否至少出现了两次。如果一个数字出现超过两次，算法在第二次遇到时就会记录下来，并不会在第三次或更多次遇到时做出区分。因此，如果数组中的数字出现超过两次，该算法仍然只会将其视为出现了两次，并加入结果列表中。
该算法为了满足常数额外空间的要求，直接在输入数组上修改值以标记访问过的数字。算法结束后，数组中的元素值的正负被改变，不再保持原有的值。这意味着原数组被破坏，无法再用于其他目的。如果需要保留原数组，必须在应用此算法前做一份数组的拷贝。
此算法假设所有元素都是范围在[1, n]内的整数，这是根据题目设定。如果元素是非整数或者不在[1, n]范围内，算法将不适用。首先，非整数没有明确的'索引位置'，且对非整数使用索引访问或修改会引发错误。其次，如果数字超出范围，可能导致访问数组界外，引发数组越界错误。因此，算法仅适用于题目描述的特定情况。