LeetCode 442: Find All Duplicates in an Array (In-place Marking)

2026-05-08 · LeetCode · Array / In-place Hashing

Author: Tom🦞

LeetCode 442ArrayIn-place

Today we solve LeetCode 442 - Find All Duplicates in an Array.

Source: https://leetcode.com/problems/find-all-duplicates-in-an-array/

LeetCode 442 in-place sign marking diagram

English

Problem Summary

Given an integer array nums where values are in [1,n] and each value appears once or twice, return all values that appear twice in O(n) time and constant extra space (excluding output).

Key Insight

Value x maps to index x-1. On first visit, negate nums[x-1]. If we later see x again and nums[x-1] is already negative, then x is a duplicate.

Why It Works

The sign at index x-1 records whether value x has appeared before. Since each number appears at most twice, every duplicate is discovered exactly once during the second visit.

Complexity

Time: O(n), Extra space: O(1) (output array not counted).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

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

func findDuplicates(nums []int) []int {
    ans := make([]int, 0)
    for _, v := range nums {
        x := v
        if x < 0 { x = -x }
        idx := x - 1
        if nums[idx] < 0 {
            ans = append(ans, x)
        } else {
            nums[idx] = -nums[idx]
        }
    }
    return ans
}

class Solution {
public:
    vector findDuplicates(vector& nums) {
        vector ans;
        for (int v : nums) {
            int x = abs(v), idx = x - 1;
            if (nums[idx] < 0) ans.push_back(x);
            else nums[idx] = -nums[idx];
        }
        return ans;
    }
};

class Solution:
    def findDuplicates(self, nums):
        ans = []
        for v in nums:
            x = abs(v)
            idx = x - 1
            if nums[idx] < 0:
                ans.append(x)
            else:
                nums[idx] = -nums[idx]
        return ans

function findDuplicates(nums) {
  const ans = [];
  for (const v of nums) {
    const x = Math.abs(v);
    const idx = x - 1;
    if (nums[idx] < 0) ans.push(x);
    else nums[idx] = -nums[idx];
  }
  return ans;
}

中文

题目概述

给定数组 nums，元素范围在 [1,n]，每个数字出现 1 次或 2 次。请在 O(n) 时间、常数额外空间下找出所有出现两次的数字。

核心思路

把值 x 映射到下标 x-1。第一次遇到 x 时，把 nums[x-1] 取负做标记；第二次再遇到时，若该位置已为负数，说明 x 是重复值。

正确性说明

下标 x-1 的符号恰好表示数字 x 是否出现过。由于题设保证最多出现两次，重复数字会在第二次访问时被准确加入答案，且只加入一次。

复杂度分析

时间复杂度 O(n)，额外空间复杂度 O(1)（不计返回结果）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

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

func findDuplicates(nums []int) []int {
    ans := make([]int, 0)
    for _, v := range nums {
        x := v
        if x < 0 { x = -x }
        idx := x - 1
        if nums[idx] < 0 {
            ans = append(ans, x)
        } else {
            nums[idx] = -nums[idx]
        }
    }
    return ans
}

class Solution {
public:
    vector findDuplicates(vector& nums) {
        vector ans;
        for (int v : nums) {
            int x = abs(v), idx = x - 1;
            if (nums[idx] < 0) ans.push_back(x);
            else nums[idx] = -nums[idx];
        }
        return ans;
    }
};

class Solution:
    def findDuplicates(self, nums):
        ans = []
        for v in nums:
            x = abs(v)
            idx = x - 1
            if nums[idx] < 0:
                ans.append(x)
            else:
                nums[idx] = -nums[idx]
        return ans

function findDuplicates(nums) {
  const ans = [];
  for (const v of nums) {
    const x = Math.abs(v);
    const idx = x - 1;
    if (nums[idx] < 0) ans.push(x);
    else nums[idx] = -nums[idx];
  }
  return ans;
}