给定一个数组,包含从 1 到 N 所有的整数,但其中缺了两个数字,O(N) 时间内用 O(1) 的空间,找出来两个数字,
例如:
输入: [1]
输出: [2,3]
三个方法
01第一个就是数学 的方法
正整数数列求和 s1 = n(n+1)/2
平方和 s2 = n(n+1)(2n+1)/6
先算出期望的s1,s2,在遍历数组并在s1,s2中减去每项和它的平方,最后得到的就是,小时的两个数字的和以及它们的平方和,然后用一些简单的数学知识就能解出2数。
02第二个就是hash
若是题目没有要求O(1)空间,那么直观的想法就是新建一个size为nums.size()+2的新数组,然后遍历nums,将nums中的每个数字映射到新数组中下标 和每个数字相同的位置,然后遍历新数组,找到缺失的两个数字。