图解LeetCode——面试题 17.19. 消失的两个数字（难度：困难）

一、题目

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

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

二、示例

2.1> 示例 1:

【输入】 [1]
【输出】 [2,3]

2.2> 示例 2:

【输入】 [2,3]
【输出】 [1,4]

提示：

• nums.length <= 30000

三、解题思路

根据题目中的描述，有两个非常重要的信息，分别是：

1> 入参nums数组包含了从1到N的所有整数，即：没有重复元素。
2> 其中缺失了两个数字。

所以，我们实际上数组（我称之为：“完整体”）的长度应该是：num数组长度 + 2。那么，以下图为例，计算完整体的总和（数学家小高斯巧解一加到一百的故事），我们就可以通过：(1 + 10) * 数组长度 / 2 ，即：55。 计算公式为：**((totalLength + 1) * totalLength) / 2** 或 ((totalLength + 1) * totalLength) >> 1。然后我们再遍历nums数组，获得所有元素总和等于44，那么我们就可以知道这个位置的元素x和元素y的总和就是：55 - 44 = 11了。

既然我们已经知道 x + y = 11了，下面我们就想方设法去确定其具体的值是什么了。首先，我们获取x和y的中心点，即： 11 / 2 = 5，那么，既然是中心点，并且根据题意，数组中的元素不会有重复值，所以，肯定是一个小于5（指定为x），另一个大于5（指定为y）。

那么，我们遍历所有nums中小于等于5的元素（即：1、3、2、5），获取总和等于11。在获得完全体中小于等于5的元素（即：1、2、3、4、5）总和于15，那么他们的差值就是x了，即：x = 15 - 11 = 4。

而我们前面已经计算过x + y = 11，由于x等于4，则y = 7。具体操作，请见下图所示：

四、代码实现

class Solution {
    public int[] missingTwo(int[] nums) {
        int totalLength = nums.length + 2;
        int totalSum = ((totalLength + 1) * totalLength) >> 1;
        for (int num : nums) totalSum -= num;
        int missingHalf = totalSum >> 1;
        int missingHalfSum = ((missingHalf + 1) * missingHalf) >> 1;
        for (int num : nums) 
            if (num <= missingHalf) 
                missingHalfSum -= num;
        return new int[] {missingHalfSum, totalSum - missingHalfSum};
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」