Java算法——数组中重复的数据（LeetCode第442题）

给你一个长度为 n 的整数数组 nums ，其中 nums 的所有整数都在范围 [1, n] 内，且每个整数出现 一次 或 两次 。请你找出所有出现 两次 的整数，并以数组形式返回。

你必须设计并实现一个时间复杂度为 O(n) 且仅使用常量额外空间的算法解决此问题。

因为题目中规定了nums 的所有整数都在范围 [1, n] 内，因此 nums 的取值范围正好与 nums 的下标[0, n - 1]能相互映射。

利用正负号来标识数组元素是否重复，那么每次判断 nums[nums[i] - 1] 的值是否为正数，如果为正数则将其取反变为负数。

数组一路往后遍历如果发现 nums[nums[i] - 1] 的值为负数那么说明已经在前面已经出现过一次了 此时就直接添加进返回数组中就是。

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