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

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

题目描述：

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

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

示例 1:

输入: [1]
输出: [2,3]

示例 2:

输入: [2,3]
输出: [1,4]

提示：

• nums.length <= 30000

解法：等差数列

我们可以通过等差数列求和公式 len * (len + 1) / 2，先计算出不缺失时数组之和sum，在依次减去现有元素，计算出缺失元素之和temp。由于元素各不相同，那个缺失的两个元素一定在 temp / 2 的两边。

下面问题就转为了，在数组[1,temp /2]中找到缺失的一个数字s。另一个数字通过 temp - s即可得到。

代码：

class Solution {
    public int[] missingTwo(int[] nums) {
        int len = nums.length + 2;
        int sum = len * (len + 1) / 2;
        int temp = sum;
        for (int num : nums) {
            temp -= num;
        }
        int t = temp / 2;
        int s = t * (t + 1) / 2;
        for (int num : nums) {
            if (num <= t) {
                s -= num;
            }
        }
        return new int[]{s, temp - s};
    }
}