【程序员面试金典】17.19. 消失的两个数字

文章目录

• 1.异或
• 2.求和

题目链接：https://class="superseo">leetcode.cn/problems/missing-two-lcci/

1.异或

C++ 代码如下：

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size() + 2;

        int xorsum = 0;
        for (auto &x : nums) {
            xorsum ^= x;
        }
        for (int x = 1; x <= n; x++) {
            xorsum ^= x;
        }

        int lowbit = xorsum & -xorsum;

        int x1 = 0;
        for (auto &x : nums) {
            if (x & lowbit) {
                x1 ^= x;
            }
        }
        for (int x = 1; x <= n; x++) {
            if (x & lowbit) {
                x1 ^= x;
            }
        }

        int x2 = xorsum ^ x1;

        return {x1, x2};
    }
};

2.求和

C++ 代码如下：

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size() + 2;

        int sum = n * (n + 1) >> 1;
        for (auto &x : nums) {
            sum -= x;
        }

        int mid = sum >> 1;

        int leftsum = mid * (mid + 1) >> 1;
        for (auto &x : nums) {
            if (x <= mid) {
                leftsum -= x;
            }
        }

        return {leftsum, sum - leftsum};
    }
};