LeetCode 解題筆記：3731. Find Missing Elements

作者：王一哲
日期：2026年8月4日


LeetCode 題目連結：3731. Find Missing Elements

解題想法

簡單題。題目給一個陣列 $nums$，其中的數字皆不相同，先找出 $nums$ 之中的最小值與最大值，再找出最小值、最大值之間不在 $nums$ 之中的整數，將缺少的整數排序後再回傳，如果沒有缺少的整數則回傳空陣列。我們可以用 Python 的 max、min 或是 C++ 的 max_element、min_element 找出最大值 $high$ 與最小值 $low$。為了標記區間 $[low, high]$ 所有的數字是否在 $nums$ 之中，可以用一個長度為 $high - low + 1$ 陣列 $found$，將 $nums$ 之中所有數字 $num$ 標示為 $found[num - low] = True$。也可以將 $nums$ 轉成 Python 的 set 或是 C++ 的 unordered_set，直接用 in 或是 count 檢查數字是否在 $nums$ 之中。兩者寫法的速度都很快。

Python 程式碼

用串列標記狀態。Runtime: 0 ms, beats 100.00%. Memory: 19.45 MB, beats 18.85%.

class Solution:
    def findMissingElements(self, nums: List[int]) -> List[int]:
        low, high = min(nums), max(nums)  # 最小值、最大值
        found = [False] * (high - low + 1)  # 是否有這個值
        for num in nums:  # 更新狀態
            found[num - low] = True
        
        ans = []  # 缺少的值
        for i in range(low + 1, high):
            if not found[i - low]:
                ans.append(i)
        return ans

用串列標記狀態，合併産生答案的程式碼。Runtime: 0 ms, beats 100.00%. Memory: 19.26 MB, beats 55.74%.

class Solution:
    def findMissingElements(self, nums: List[int]) -> List[int]:
        low, high = min(nums), max(nums)  # 最小值、最大值
        found = [False] * (high - low + 1)  # 是否有這個值
        for num in nums:  # 更新狀態
            found[num - low] = True
        
        return [i for i in range(low + 1, high) if not found[i - low]]

用 set 檢查數字是否在 $nums$ 之中。Runtime: 0 ms, beats 100.00%. Memory: 19.29 MB, beats 55.74%.

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

用 set 檢查數字是否在 $nums$ 之中，合併産生答案的程式碼。Runtime: 0 ms, beats 100.00%. Memory: 19.37 MB, beats 18.85%.

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

C++ 程式碼

用陣列標記狀態。Runtime: 0 ms, beats 100.00%. Memory: 32.33 MB, beats 54.61%.

class Solution {
public:
    vector<int> findMissingElements(vector<int>& nums) {
        int low = *min_element(nums.begin(), nums.end());
        int high = *max_element(nums.begin(), nums.end());
        vector<bool> found (high - low + 1, false);
        for(int num : nums) found[num - low] = true;
        vector<int> ans;
        for(int i = low + 1; i < high; i++) {
            if (!found[i - low]) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

用 unordered_set 檢查數字是否在 $nums$ 之中。Runtime: 8 ms, beats 12.18%. Memory: 33.76 MB, beats 17.56%.

class Solution {
public:
    vector<int> findMissingElements(vector<int>& nums) {
        int low = *min_element(nums.begin(), nums.end());
        int high = *max_element(nums.begin(), nums.end());
        unordered_set<int> num_set (nums.begin(), nums.end());
        vector<int> ans;
        for(int i = low + 1; i < high; i++) {
            if (num_set.count(i) == 0) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

C 語言程式碼

用陣列標記狀態。Runtime: 0 ms, beats 100.00%. Memory: 13.22 MB, beats 18.45%.

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* findMissingElements(int* nums, int numsSize, int* returnSize) {
    // 找出最小值、最大值，標記數字是否在 nums 之中
    int low = 1000000000, high = -1000000000, found[101] = {0};
    for(int i = 0; i < numsSize; i++) {
        int num = nums[i];
        if (num < low) low = num;
        if (num > high) high = num;
        found[num] = 1;
    }
    // 找出缺少的數字數量
    int cnt = 0;
    for(int i = low + 1; i < high; i++) {
        if (found[i] == 0) {
            cnt++;
        }
    }
    // 更新 retrunSize 為 cnt，並建立長度為 cnt 的 array，於 array 填入缺少的數字
    *returnSize = cnt;
    int idx = 0, *ans = malloc(cnt * sizeof(int));
    for(int i = low + 1; i < high; i++) {
        if (found[i] == 0) {
            ans[idx] = i;
            idx++;
        }
    }
    return ans;
}