LeetCode-面试题 17.19. 消失的两个数字【求和】
2023-09-14 09:01:27 时间
题目描述:
给定一个数组,包含从 1 到 N 所有的整数,但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗?
以任意顺序返回这两个数字均可。
示例 1:
输入: [1]
输出: [2,3]
示例 2:
输入: [2,3]
输出: [1,4]
提示:
nums.length <= 30000
解题思路一:1.将nums求和,利用等差数列求和公式得长度为n的数组的和,两个相减便得到缺失的两个数的和sumTwo。2.l=sumTwo/2,因为两个数不相等,那么一个数小于等于l,另一个数大于等于l;首先求nums中小于等于l的数的和,然后再用一次等差数列求和公式便得到左边的缺失的数。最后可以得出结果。
class Solution {
public:
vector<int> missingTwo(vector<int>& nums) {
int n=nums.size()+2;
long sum=0;
for(int num:nums) sum+=num;
int sumTwo=n*(n+1)/2-sum,l=sumTwo/2;
sum=0;
for(int num:nums)
if(num<=l) sum+=num;
int left=l*(l+1)/2-sum;
return {left,sumTwo-left};
}
};
解题思路二:暂无
解题思路三:暂无