1. leetcode442 数组中重复的元素

解法一：使用负数，利用原始数组来实现。时间复杂度：O(1)，空间复杂度O(1)

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

解法二：+n，利用原始数组来实现。时间复杂度：O(1)，空间复杂度O(1)

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int n = nums.length;
        //对原数组作预处理
        for(int i = 0; i < n; i++){
            int index = (nums[i] - 1) % n;
            nums[index] += n;
        }
        for(int i = 0; i < n; i++){
            if(nums[i] > 2 * n)
                res.add(i + 1);
        }
        return res;
    }
}

2. leetcode448 找到数组中所有消失的数字

解法一：+n，利用原始数组来实现。时间复杂度：O(1)，空间复杂度O(1)

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int n = nums.length;
        for(int i = 0; i < n; i++){
            int index = (nums[i] - 1) % n;
            nums[index] += n;
        }
        for(int i = 0; i < n; i++){
            if(nums[i] <= n)
                res.add(i + 1);
        }
        return res;
    }
}