Intuition#

核心思路：XOR 所有索引和所有元素，成對的會抵消，留下缺少的數字。

• 排序後找不連續的位置可行，但時間 O(n log n)
• 數學法：預期總和 n*(n+1)/2 減去實際總和就是缺少的數字
• XOR 法：將 0~n 和 nums 中所有數字 XOR，成對出現的會抵消為 0

Approaches#

1: 數學求和#

• 概念: 利用等差數列求和公式，預期總和減去陣列實際總和即為缺少的數字
• 時間複雜度: O(n) - 遍歷陣列一次
• 空間複雜度: O(1)

class Solution {
    fun missingNumber(nums: IntArray): Int {
        val n = nums.size
        val expectedSum = n * (n + 1) / 2
        val actualSum = nums.sum()
        return expectedSum - actualSum
    }
}

⭐2: XOR#

• 概念: 將索引 0~n 和陣列所有元素一起 XOR，成對的會抵消，剩下的就是缺少的數字
• 時間複雜度: O(n) - 遍歷陣列一次
• 空間複雜度: O(1)

class Solution {
    fun missingNumber(nums: IntArray): Int {
        var xor = nums.size
        for (i in nums.indices) {
            xor = xor xor i xor nums[i]
        }
        return xor
    }
}

數學求和法在 n 很大時可能有整數溢位風險（雖然 LeetCode 測資範圍內不會），XOR 法則完全沒有溢位問題。

class Solution {
    fun missingNumber(nums: IntArray): Int {
        nums.sort()
        for (i in nums.indices) {
            if (nums[i] != i) return i
        }
        return nums.size
    }
}

🔑 Takeaways#

• Pattern: XOR 消除配對，與 Single Number 同屬一類
• 關鍵技巧: 當問題涉及「找缺失 / 找重複」且數字範圍明確時，XOR 和數學求和都是 O(1) 空間的好方法