Easy

题目描述

给你一个由唯一整数组成的整数数组 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

解题思路

这道题要求找出数组中缺失的元素，核心思路是：

  1. 确定范围：首先找到数组中的最小值和最大值，这两个值确定了应该包含的完整范围。

  2. 解法一：哈希表查找（推荐）

    • 将数组中的所有元素放入哈希集合中，实现O(1)查找
    • 遍历[min, max]范围内的每个数字，检查是否在哈希集合中
    • 不存在的数字就是缺失的元素

  3. 解法二：数组标记

    • 创建一个布尔数组标记哪些数字存在
    • 遍历原数组标记存在的元素
    • 再次遍历找出未标记的元素

  4. 解法三：排序后比较

    • 先排序数组，然后逐一比较相邻元素
    • 如果相邻元素差值大于1，说明中间有缺失

哈希表解法在时间和空间复杂度上都比较优秀，且代码简洁易懂，是最推荐的解法。

代码实现

class Solution {
public:
    vector<int> findMissingElements(vector<int>& nums) {
        int minVal = *min_element(nums.begin(), nums.end());
        int maxVal = *max_element(nums.begin(), nums.end());
        
        unordered_set<int> numSet(nums.begin(), nums.end());
        vector<int> result;
        
        for (int i = minVal; i <= maxVal; i++) {
            if (numSet.find(i) == numSet.end()) {
                result.push_back(i);
            }
        }
        
        return result;
    }
};

class Solution:
    def findMissingElements(self, nums: List[int]) -> List[int]:
        min_val = min(nums)
        max_val = max(nums)
        
        num_set = set(nums)
        result = []
        
        for i in range(min_val, max_val + 1):
            if i not in num_set:
                result.append(i)
        
        return result

public class Solution {
    public IList<int> FindMissingElements(int[] nums) {
        int minVal = nums.Min();
        int maxVal = nums.Max();
        
        HashSet<int> numSet = new HashSet<int>(nums);
        List<int> result = new List<int>();
        
        for (int i = minVal; i <= maxVal; i++) {
            if (!numSet.Contains(i)) {
                result.Add(i);
            }
        }
        
        return result;
    }
}

var findMissingElements = function(nums) {
    const minVal = Math.min(...nums);
    const maxVal = Math.max(...nums);
    
    const numSet = new Set(nums);
    const result = [];
    
    for (let i = minVal; i <= maxVal; i++) {
        if (!numSet.has(i)) {
            result.push(i);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型哈希表解法
时间复杂度O(n + k)，其中 n 是数组长度，k 是范围大小
空间复杂度O(n)，用于存储哈希集合