給定一個包含
[0, n]範圍內n個不重複數字的陣列nums，找出該範圍內缺少的那個數字。
Example:
Input: nums = [3,0,1] Output: 2
Intuition
TIP
核心思路：XOR 所有索引和所有元素，成對的會抵消，留下缺少的數字。
- 排序後找不連續的位置可行，但時間 O(n log n)
- 數學法：預期總和 n*(n+1)/2 減去實際總和就是缺少的數字
- XOR 法：將 0~n 和 nums 中所有數字 XOR，成對出現的會抵消為 0
Approaches
1. Math Summation — O(n) / O(1)
- Idea: 利用等差數列求和公式，預期總和減去陣列實際總和即為缺少的數字
- Time:
O(n)- 遍歷陣列一次 - Space:
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 — O(n) / O(1)
- Idea: 將索引 0~n 和陣列所有元素一起 XOR，成對的會抵消，剩下的就是缺少的數字
- Time:
O(n)- 遍歷陣列一次 - Space:
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
}
}WARNING
數學求和法在 n 很大時可能有整數溢位風險（雖然 LeetCode 測資範圍內不會），XOR 法則完全沒有溢位問題。
Note: Sorting
排序後依序檢查 nums[i] 是否等於 i：
class Solution {
fun missingNumber(nums: IntArray): Int {
nums.sort()
for (i in nums.indices) {
if (nums[i] != i) return i
}
return nums.size
}
}時間 O(n log n)，空間 O(1)（原地排序）。
🔑 Takeaways
- Pattern: XOR 消除配對，與 Single Number 同屬一類
- Key trick: 當問題涉及「找缺失 / 找重複」且數字範圍明確時，XOR 和數學求和都是 O(1) 空間的好方法