LeetCode 268 Missing Number：等差數列求和與位運算兩種解法

題目描述

給定包含 n 個不同數字的陣列 nums，取自 [0, 1, ..., n]，找出缺失的那一個數。要求線性時間、常數額外空間。

範例

Input: [0, 1, 3]
Output: 2

解法一：等差數列求和

完整數列和 sum = n*(n+1)/2，減去陣列實際和，差值即為缺失數。

class Solution {
public:
    int missingNumber(vector& nums) {
        int n = nums.size();
        int expected = n * (n + 1) / 2;
        int actual = accumulate(nums.begin(), nums.end(), 0);
        return expected - actual;
    }
};

解法二：位運算（XOR）

利用 a ^ a = 0、a ^ 0 = a、交換結合律。將索引與值配對 XOR，最後再 XOR n（因索引只到 n-1）。

class Solution {
public:
    int missingNumber(vector& nums) {
        int ans = 0;
        for (size_t i = 0; i < nums.size(); ++i) ans ^= nums[i];
        for (int i = 0; i <= nums.size(); ++i) ans ^= i;
        return ans;
    }
};

複雜度比較

總結

兩種方法皆滿足線性時間常數空間。求和法代碼最少；XOR 法更具備泛化性，適合面試展示位運算技巧。