题目描述

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

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

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

样例

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

输出:
[2,3]

算法1

(枚举) $O(n)$

这题和 287.寻找重复数 是一样的，只不过当前题要求返回多个有重复的数而已。
题目中给到条件: 1 <= a[i] <= n, 所以数值范围与索引范围之间的关系: 数值范围 - 1 = 索引范围

思想：在遍历nums 数组的时候，把遍历得到的当前数nums[i] 作为索引：nums[i]- 1，
找到nums[nums[i] - 1] 的数,然后把它取反，形成一个标记，说明这个nums[nums[i] - 1] 这个位置已经有数字占用了，如果下一次还有其他的nums[i]-1索引来到这个位置，那么就说明当前nums[i] 就是重复的那个数字。

时间复杂度

O(N)

参考文献

Java 代码

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        int n = nums.length;
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < n; i++){
            int num = Math.abs(nums[i]);
            if(nums[num - 1] > 0){
                nums[num - 1] *= -1; 
            }else{
                list.add(num);
            }
        }
        return list;
    }
}