268. 丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：

1
2
3
输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
  • nums 中的所有数字都 独一无二

无论是异或操作，还是数学求和公式，思路都很不错

Solution1：位运算

数组 nums 中有 n 个数，在这 n 个数的后面添加从 0 到 n 的每个整数，则添加了n+1 个整数，共有 2n+1 个整数。

在 2n+1 个整数中，丢失的数字只在后面 n+1 个整数中出现一次，其余的数字在前面 n 个整数中（即数组中）和后面 n+1 个整数中各出现一次，即其余的数字都出现了两次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
cclass Solution {
    // missingNumber方法接受一个整数数组nums作为参数
    public int missingNumber(int[] nums) {
        // 初始化xor为0
        int xor = 0;
        // 获取数组的长度n
        int n = nums.length;
        // 第一个for循环，将数组中所有的数字进行一次异或操作
        for (int i = 0; i < n; i++) {
            xor ^= nums[i];
        }
        // 第二个for循环，将从0到n的所有数字进行一次异或操作
        for (int i = 0; i <= n; i++) {
            xor ^= i;
        }
        // 由于一个数字异或它自己会等于0，且异或操作满足交换律和结合律
        // 上述两次循环完成后，所有没有缺失的数字都被异或两次，结果为0
        // 唯一缺失的数字只被异或了一次，所以最终xor的值就是那个缺失的数字
        return xor;
    }
}

Solution2：数学

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int total = n * (n + 1) / 2;
        int arrSum = 0;
        for (int i = 0; i < n; i++) {
            arrSum += nums[i];
        }
        return total - arrSum;
    }
}