Programming

Leetcode-442. Find All Duplicates in an Array

Leetcode-442. Find All Duplicates in an Array

<解題>


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(index + 1); // 如果该位置的元素已经是负数,说明之前出现过,将其加入结果列表
        }

        nums[index] = -nums[index]; // 将该位置的元素变为负数,表示已经出现过一次
    }
    return res; // 返回重复元素的列表
}

Time: O(n) Space: O(1)