3731.找出缺失的元素：哈希 / 排序

【LetMeFly】3731.找出缺失的元素：哈希 / 排序

力扣题目链接：https://leetcode.cn/problems/find-missing-elements/

给你一个整数数组 nums ，数组由若干 互不相同 的整数组成。

数组 nums 原本包含了某个范围内的 所有整数 。但现在，其中可能 缺失 部分整数。

该范围内的 最小 整数和 最大 整数仍然存在于 nums 中。

返回一个 有序 列表，包含该范围内缺失的所有整数，并 按从小到大排序。如果没有缺失的整数，返回一个 空 列表。

 

示例 1：

输入： nums = [1,4,2,5]

输出： [3]

解释：

最小整数为 1，最大整数为 5，因此完整的范围应为 [1,2,3,4,5]。其中只有 3 缺失。

示例 2：

输入： nums = [7,8,6,9]

输出： []

解释：

最小整数为 6，最大整数为 9，因此完整的范围为 [6,7,8,9]。所有整数均已存在，因此没有缺失的整数。

示例 3：

输入： nums = [5,1]

输出： [2,3,4]

解释：

最小整数为 1，最大整数为 5，因此完整的范围应为 [1,2,3,4,5]。缺失的整数为 2、3 和 4。

 

提示：

• 2 <= nums.length <= 100
• 1 <= nums[i] <= 100

解题方法一：哈希表

创建一个大小为$100$的布尔类型的集合作为哈希表统计每个数字是否出现过。遍历一次原始数组可得到都出现过哪些数字，再遍历一遍哈希表可得都缺少哪些数字。

• 时间复杂度$O(len(nums)+M)$
• 空间复杂度$O(M)$

AC代码

C++

/*
 * @LastEditTime: 2026-08-04 11:04:35
 */
class Solution {
public:
    vector<int> findMissingElements(vector<int>& nums) {
        vector<bool> ma(101);
        int m = nums[0], M = nums[0];
        for (int t : nums) {
            m = min(m, t);
            M = max(M, t);
            ma[t] = true;
        }
        
        vector<int> ans;
        ans.reserve(M - m + 1 - nums.size());
        for (int i = m + 1; i < M; i++) {
            if (!ma[i]) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

解题方法二：排序

对$nums$数组排序，用变量$i$从最小值到最大值枚举，若排序后数组的下一个元素和$i$不相等则说明缺失。

• 时间复杂度$O(len(nums)\log len(nums) + M)$
• 空间复杂度$O(\log len(nums))$

AC代码

C++

/*
 * @LastEditTime: 2026-08-04 11:08:22
 */
class Solution {
public:
    vector<int> findMissingElements(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int m = nums[0], M = nums.back(), n = nums.size();
        vector<int> ans;
        ans.reserve(M - m + 1 - n);
        for (int i = m, idx = 0; i <= M; i++) {
            if (idx == n || nums[idx] != i) {
                ans.push_back(i);
            } else {
                idx++;
            }
        }
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源