【数组篇】day09_442. 数组中重复的数据

题解一：

思路：

• 首先nums中的元素在[1,n]之内，并且长度为n，考虑到题目要求空间复杂度为常数，需要将nums本身作为字典表，记录每个元素出现的次数
• 元素值看作字典表的索引，即x = num-1
• 遍历nums数组，依次得到字典表的索引x。此时有两种情况：nums[x] > 0（第一次遍历到num时，必满足此条件）->nums[x]取反；当nums[x] <0时，说明第二次遍历到num，此时num = x+1。

复杂度：

• 时间复杂度：O(n) 
• 空间复杂度：O(1)

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