題目描述

給定包含 0, 1, 2, ..., n 中 n 個不同數字的數組，找出缺失的那一個。要求 O(n) 時間、O(1) 額外空間。

示例： [0, 1, 3] → 2

解法一：數學求和（直觀但有溢出風險）

總和 n(n+1)/2 減去數組和即為缺失數。注意整數溢出：n≤10⁴ 時 int 安全，更大需用 long。

// C++ 版本
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        long total = 1L * n * (n + 1) / 2; // 防溢出
        long sum = 0;
        for (int x : nums) sum += x;
        return (int)(total - sum);
    }
};

// Java 版本
public class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int total = n * (n + 1) / 2; // Java int 32位足夠
        for (int x : nums) total -= x;
        return total;
    }
}

解法二：異或運算（無溢出、純位運算）

性質：a ^ a = 0，a ^ 0 = a。將索引 0~n 與數組元素全部異或，成對抵消，剩下缺失數。

// C++ 版本
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int miss = nums[0] ^ 0;
        for (int i = 1; i < nums.size(); i++) {
            miss ^= nums[i];
            miss ^= i;
        }
        return miss ^ nums.size(); // 最後異或 n
    }
};

// Java 版本
public class Solution {
    public int missingNumber(int[] nums) {
        int miss = nums[0] ^ 0;
        for (int i = 1; i < nums.length; i++) {
            miss ^= nums[i];
            miss ^= i;
        }
        return miss ^ nums.length;
    }
}

解法三：原地置換（循環排序，修改輸入數組）

將每個數字放到對應索引位置，最終遍歷找到 nums[i] != i 的位置。時間 O(n)，空間 O(1)，但修改輸入。

複雜度總結

推薦： 異或法最優雅、無副作用、無溢出風險。