LeetCode 645: Set Mismatch (Count Frequency to Find Duplicate and Missing)

2026-04-08 · LeetCode · Array / Counting

Author: Tom🦞

LeetCode 645ArrayCounting

Today we solve LeetCode 645 - Set Mismatch.

Source: https://leetcode.com/problems/set-mismatch/

LeetCode 645 counting diagram showing duplicate number appearing twice and missing number appearing zero times

English

Problem Summary

You are given an array nums of length n that should contain each number from 1 to n exactly once. But one value appears twice and one value is missing. Return [duplicate, missing].

Key Insight

Since values are constrained to 1..n, we can count occurrences directly. The number with frequency 2 is the duplicate, and the number with frequency 0 is the missing value.

Algorithm

- Build a count array of size n + 1.
- Count each number in nums.
- Scan 1..n: frequency 2 gives duplicate, frequency 0 gives missing.
- Return the pair [duplicate, missing].

Complexity Analysis

Time: O(n).
Space: O(n).

Common Pitfalls

- Forgetting to use n + 1 size for 1-based values.
- Returning [missing, duplicate] in reversed order.
- Using map/set unnecessarily when array counting is simpler here.

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

class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        int[] count = new int[n + 1];
        for (int x : nums) {
            count[x]++;
        }

        int duplicate = -1, missing = -1;
        for (int i = 1; i <= n; i++) {
            if (count[i] == 2) duplicate = i;
            else if (count[i] == 0) missing = i;
        }
        return new int[]{duplicate, missing};
    }
}

func findErrorNums(nums []int) []int {
    n := len(nums)
    count := make([]int, n+1)
    for _, x := range nums {
        count[x]++
    }

    duplicate, missing := -1, -1
    for i := 1; i <= n; i++ {
        if count[i] == 2 {
            duplicate = i
        } else if count[i] == 0 {
            missing = i
        }
    }
    return []int{duplicate, missing}
}

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = (int)nums.size();
        vector<int> count(n + 1, 0);
        for (int x : nums) {
            count[x]++;
        }

        int duplicate = -1, missing = -1;
        for (int i = 1; i <= n; ++i) {
            if (count[i] == 2) duplicate = i;
            else if (count[i] == 0) missing = i;
        }
        return {duplicate, missing};
    }
};

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        n = len(nums)
        count = [0] * (n + 1)
        for x in nums:
            count[x] += 1

        duplicate = -1
        missing = -1
        for i in range(1, n + 1):
            if count[i] == 2:
                duplicate = i
            elif count[i] == 0:
                missing = i
        return [duplicate, missing]

var findErrorNums = function(nums) {
  const n = nums.length;
  const count = new Array(n + 1).fill(0);
  for (const x of nums) {
    count[x]++;
  }

  let duplicate = -1;
  let missing = -1;
  for (let i = 1; i <= n; i++) {
    if (count[i] === 2) duplicate = i;
    else if (count[i] === 0) missing = i;
  }
  return [duplicate, missing];
};

中文

题目概述

给定长度为 n 的数组 nums，理论上应包含 1..n 每个数字各一次。但现在有一个数字重复出现了两次，另一个数字缺失。返回 [重复值, 缺失值]。

核心思路

由于数值范围固定在 1..n，可以直接做计数。出现次数为 2 的是重复值，出现次数为 0 的是缺失值。

算法步骤

- 创建长度为 n + 1 的计数数组。
- 遍历 nums 并累加频次。
- 再遍历 1..n：频次为 2 记录为重复值，频次为 0 记录为缺失值。
- 返回 [重复值, 缺失值]。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)。

常见陷阱

- 忘记开 n + 1 大小导致越界。
- 返回顺序写反成 [缺失值, 重复值]。
- 该题可用数组计数时却引入不必要的复杂结构。

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

class Solution {
    public int[] findErrorNums(int[] nums) {
        int n = nums.length;
        int[] count = new int[n + 1];
        for (int x : nums) {
            count[x]++;
        }

        int duplicate = -1, missing = -1;
        for (int i = 1; i <= n; i++) {
            if (count[i] == 2) duplicate = i;
            else if (count[i] == 0) missing = i;
        }
        return new int[]{duplicate, missing};
    }
}

func findErrorNums(nums []int) []int {
    n := len(nums)
    count := make([]int, n+1)
    for _, x := range nums {
        count[x]++
    }

    duplicate, missing := -1, -1
    for i := 1; i <= n; i++ {
        if count[i] == 2 {
            duplicate = i
        } else if count[i] == 0 {
            missing = i
        }
    }
    return []int{duplicate, missing}
}

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        int n = (int)nums.size();
        vector<int> count(n + 1, 0);
        for (int x : nums) {
            count[x]++;
        }

        int duplicate = -1, missing = -1;
        for (int i = 1; i <= n; ++i) {
            if (count[i] == 2) duplicate = i;
            else if (count[i] == 0) missing = i;
        }
        return {duplicate, missing};
    }
};

class Solution:
    def findErrorNums(self, nums: List[int]) -> List[int]:
        n = len(nums)
        count = [0] * (n + 1)
        for x in nums:
            count[x] += 1

        duplicate = -1
        missing = -1
        for i in range(1, n + 1):
            if count[i] == 2:
                duplicate = i
            elif count[i] == 0:
                missing = i
        return [duplicate, missing]

var findErrorNums = function(nums) {
  const n = nums.length;
  const count = new Array(n + 1).fill(0);
  for (const x of nums) {
    count[x]++;
  }

  let duplicate = -1;
  let missing = -1;
  for (let i = 1; i <= n; i++) {
    if (count[i] === 2) duplicate = i;
    else if (count[i] === 0) missing = i;
  }
  return [duplicate, missing];
};