【LeetCode - Java】268. 丢失的数字 （简单）

1. 题目描述2. 解题思路3. 代码实现

3.1 求和相减3.2 公式求和相减3.3 位运算3.4 对比

既然已经知道数组中的数字是在0到n的范围内，那么就可以把0到n累加起来，然后减去数组中的数的累加和，就可以得出缺的数是什么了。0到n可以累加求和，也可以使用公式求和，两种方法区别不大。

除此以外，我们还可以使用异或运算的方法，因为a⊕a=0，b⊕0=b，因此把数组中的数与0到n异或起来，就可以得出缺的那个数字，因为除了缺的数字以外，其他数字都出现了两遍。

public int missingNumber(int[] nums) {
        int sum = 0, total = nums.length;
        for (int i = 0; i < nums.length; i++) {
            total += i;
            sum += nums[i];
        }
        return total - sum;
    }

public int missingNumber(int[] nums) {
        int length = nums.length;
        int sum = 0, total = (1 + length) * length / 2;
        for (int num : nums) {
            sum += num;
        }
        return total - sum;
    }

public int missingNumber(int[] nums) {
        int length = nums.length;
        int sum = length;
        for (int i = 0; i < length; i++) {
            sum ^= nums[i] ^ i;
        }
        return sum;
    }

三种方法的时间复杂度都是O(n)，空间复杂度都是O(1)，整体表现差别不大。