消失的两个数字

public int[] missingTwo(int[] nums) {
    // 1 + 2 + 3 +...+ n = n(n + 1) / 2
    // 1 ^ 1 + 2 ^ 2 + ... + n ^ n = n(n + 1)(2n + 1) / 6
    int n = nums.length + 2;
    int sum = n * (n + 1) >> 1;
    // 注意溢出, 所以循环的时候直接做差值
    // long squareSum = n * (n + 1) * (2 * n + 1) / 6;
    long squareSum = 0;
    for (int i = 0; i <= n; i++) {
        if (i < nums.length) {
            sum -= nums[i];
            squareSum -= nums[i] * nums[i];
        }
        squareSum += i * i;
    }
    // x1 + x2 = sum
    // x1 ^ 2 + x2 ^ 2 = squareSum
    // 2x1x2 = (x1 + x2) ^ 2 - (x1 ^ 2 + x2 ^ 2) = sum * sum - squareSum
    // (x1 - x2) ^ 2 = x1 ^ 2 + x2 ^ 2 - 2x1x2 = squareSum - (sum * sum -squareSum) = 2 * squareSum - sum * sum
    // x1 - x2 = Math.sqrt(squareSum * 2 - sum * sum)
    // x1 = (x1 + x2 + (x1 - x2)) / 2
    // x2 = (x1 + x2 - (x1 - x2)) / 2
    long diff = (long) Math.sqrt(squareSum * 2 - sum * sum);
    return new int[]{(int) (sum - diff) / 2, (int) (sum + diff) / 2};
}

public int[] missingTwo(int[] nums) {
    int n = nums.length + 2;
    int total = (1 + n) * n >> 1;
    for (int num : nums) total -= num;
	// 求平均值, 两个数字必定一个大于平均值一个小于平均值
    int avg = total >> 1;
    int subTotal = (1 + avg) * avg >> 1;
    for (int num : nums) {
        if (num <= avg) subTotal -= num;
    }
    return new int[]{subTotal, total - subTotal};
}

public int[] missingTwo(int[] nums) {
    int n = nums.length + 2;
    int xorSum = 0;
    for (int num : nums) xorSum ^= num;
    // 注意从 1 开始
    for (int i = 1; i <= n; i++) xorSum ^= i;
    int one = 0;
    // 最低位的 1, 相当于 Integer.lowestOneBit()
    int lowest = (xorSum == Integer.MIN_VALUE) ? xorSum : xorSum & -xorSum;
    // 按 xorSum 最低位的 1 所在位置为 0 或 1 分组
    for (int num : nums) if ((num & lowest) == 0) one ^= num;
    for (int i = 1; i <= n; i++) if ((i & lowest) == 0) one ^= i;
    return new int[]{one, xorSum ^ one};
}

public int[] missingTwo(int[] nums) {
    // 标记 n + 1, n + 2 是否出现
    int[] temp = new int[]{1, 1};
    int n = nums.length;
    // nums[i] 出现则将 Math.abs(nums[i]) - 1 下标对应的值 * -1, 也就是变成负数
    // 反之, 如果 nums[i] 为负数, 则证明数字 i + 1 出现过
    for (int i = 0; i < n; i++) {
        int index = Math.abs(nums[i]) - 1;
        if (index < n) nums[index] *= -1;
        else temp[index - n] = -1;
    }
    int[] ans = new int[2];
    int index = 0;
    for (int i = 0; i < n; i++) if (nums[i] > 0) ans[index++] = i + 1;
    for (int i = 0; i < 2; i++) if (temp[i] > 0) ans[index++] = n + i + 1;
    return ans;
}