leetcode面试题 17.19. 消失的两个数字_你能用on的时间内只用o1的空间找到他们吗-CSDN博客

这篇博客介绍了如何在给定包含1到N所有整数但缺失两个数字的数组中，使用O(N)的时间复杂度和O(1)的空间复杂度找出这两个缺失的数字。提供了两种解决方案：一种是通过计算累加和来确定这两个数字；另一种是利用哈希表来找出未出现的数值。这两种方法都有效地解决了问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目链接：https://leetcode-cn.com/problems/missing-two-lcci/

题意：

给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？

以任意顺序返回这两个数字均可。

方法一：先求第一个数，再求第二个数

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size()+2;//计算最大长度
        int sum=0,limits=0,sumTwo=0;
        for(auto num:nums)//计算累加
        {
            sum+=num;
        }
        sumTwo = n*(n+1)/2-sum;//计算两数的和
        limits = sumTwo/2;//算出两数的平均值
        sum=0;
        for(auto num:nums)//求出小于平均数的所有数的和
        {
            if(num<=limits)
                sum+=num;
        }
        int one = limits*(limits+1)/2-sum;//计算出小于平均数的这个数
        return {one,sumTwo-one};//返回
    }
};

方法二：哈希表

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        vector<int> ret;
        unordered_map<int,int> mp;//哈希表
        int index=0,len=nums.size();//下标,元素个数
        for(auto& num:nums)//遍历哈希表
        {
            mp[num]++;
        }
        for(int i=1;i<=len+2;i++)//再次遍历哈希表
        {
            if(mp[i]==0)//哈希值为0的数放入要返回的向量
                ret.emplace_back(i);
        }
        return ret;
    }
};