1.题目

给你一个长度为 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 <= 10⁵
1 <= nums[i] <= n
nums 中的每个元素出现一次或两次

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-all-duplicates-in-an-array

2.思路

（1）哈希表
如果不考虑空间复杂度，我们可以使用哈希表来存储数组 nums 中每个元素以及其对应出现的次数，然后再取出哈希表中出现次数为 2 的元素并将其保存到 res 中，最后再返回 res 即可。

（2）原地哈希（正负号标记）
思路参考本题官方题解。

由于数组 nums 的所有整数都在范围 [1, n] 内，而 nums 的长度正好为 n，所以我们可以构建 x - 1 ∈ [0, n - 1] 到 nums[0…n - 1] 之间的映射，通过标记 nums[x - 1] 的正负值来判断 x 出现的次数，具体步骤如下：

遍历数组 nums 中的每一个元素 x = Math.abs(nums[i])（此处要加绝对值是因为后面会改变数组 nums 中元素的符号），那么如果判断 x 是出现了 1 次还是 2 次呢？很简单，由于 x ∈ [1, n]，那么 x - 1 ∈ [0, n - 1] 正好在 nums 的下标范围内，所以我们可以进行如下判断：
① 如果 nums[x - 1] > 0，那么我们认为 x 此时只出现了一次，为了方便判断 x 下次是否出现，我们将 nums[x - 1] 取负号；
② 如果 nums[x - 1] < 0，那么这说明 nums[x - 1] 在之前已经被取过一次负号，进而可以推出 x 之前已经出现过一次，所以此时的 x 已经是第 2 次出现，故直接将其加入到 res 中；
遍历结束后，直接返回 res 即可。该方法的时间复杂度为 O(n)，空间复杂度为 O(1)（返回值的空间复杂度不计算在内）

小结：一般像这种要求使用常量额外空间且题目中与次数、次数有关的题目，我们可以首先联想到使用原地哈希，使用原地哈希的一个关键在于使用原数组（或者其它容器）作为哈希表，将原数组中的元素作为键（即看作数组中的下标），建立起适合题目条件的对应关系。

3.代码实现（Java）

//思路1————哈希表
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        Map<Integer, Integer> hashMap = new HashMap<>();
        for (int num : nums) {
            hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);
        }
        for (int num : hashMap.keySet()) {
            if (hashMap.get(num) == 2) {
                res.add(num);
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

//思路2————原地哈希（正负号标记）
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int x = Math.abs(nums[i]);
            if (nums[x - 1] > 0) {
                nums[x - 1] = -nums[x - 1];
            } else {
                res.add(x);
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15