442. duplicate data in array

One 、 Title Description

Give you a length of n Array of integers for nums , among nums All integers of are in the range [1, n] Inside , And each integer appears once or two . Please find out all that appear two The integer of , And return as an array .

You must design and implement a time complexity of O(n) And only the algorithm of constant extra space is used to solve this problem .

Example 1：

 Input ：nums = [4,3,2,7,8,2,3,1]
 Output ：[2,3]

Example 2：

 Input ：nums = [1,1,2]
 Output ：[1]

Example 3：

 Input ：nums = [1]
 Output ：[]

Two 、 Problem solving

One traverse

Sign judgment method , The numbers that appear are reversed , Then judge whether it has been reversed .

class Solution {
    
    public List<Integer> findDuplicates(int[] nums) {
    
        // This problem requires a traversal   Then use the algorithm of extra space 
        int length = nums.length;
        List<Integer> res = new ArrayList<>();
        for(int i = 0;i<length;i++){
    
            int num = Math.abs(nums[i]);
            if(nums[num-1] > 0){
    
                nums[num-1] = -nums[num-1];
            }else{
    
                res.add(num);
            }
        }
        return res;
    }
}

Time complexity ：O(n)

Spatial complexity ：O(1).