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 <= 10^5
1 <= nums[i] <= n
nums 中的每个元素出现 一次 或 两次

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-duplicates-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

因为数组长度是n，数组元素的范围为[1,n]，因此可以考虑「剑指 Offer 03. 数组中重复的数字」的思路，通过原地交换将元素放置到其应该在的位置。不过这样可能会产生重复的结果，放入set去重就可以了。

更好的做法是在数组原地进行标记，也可以叫做「原地哈希」。例如遍历到元素2，就将下标1位置的元素进行标记，标记方式很多，例如变为一个不可能的大值，这里可以加上n，也可以变为相反数，当再遇到2，还会访问到下标1，这时发现元素被标记成了原来不可能存在得知，就知道2重复出现了。

代码

原地交换(不推荐)

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        Set<Integer> set = new HashSet<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            while (nums[i] != i + 1) {
                if (nums[nums[i] - 1] == nums[i]) {
                    set.add(nums[i]);
                    break;
                }
                int tmp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = tmp;
            }
        }
        return new ArrayList<>(set);
    }
}

原地哈希 +n

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        // 将每个位置对应的下标位置元素+n
        List<Integer> res = new ArrayList<>();
        int n = nums.length;
        for (int num : nums) {
            // 根据当前元素找到的下标位置
            int j = (num - 1) % n;
            // 如果nums[j]已经>n了 那么就说明num出现了两次
            // 但是要注意因为num可能是加过n之后的 因此不能直接添加num 可以添加j+1
            if (nums[j] > n) {
                res.add(j + 1);
            }
            nums[j] += n;
        }
        return res;
    }
}

原地哈希 变相反数

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int n = nums.length;
        for (int num : nums) {
            int j = Math.abs(num) - 1;
            // j位置大于0 改为相反数
            if (nums[j] > 0) {
                nums[j] *= -1;
            } else {
                // j位置已经是负数就说明num出现两次
                res.add(j + 1);
            }
        }
        return res;
    }
}