題目描述:給定包含 [0, n] 範圍內 n 個不重複整數的陣列,找出其中缺少的那個數。
解題思路:最優雅的方法是利用高斯求和公式:[0..n] 的總和為 n*(n+1)/2,減去陣列實際元素的總和,差值即為缺失的數。也可以用 XOR:0 XOR 1 XOR ... XOR n XOR nums[0] XOR ... XOR nums[n-1],重複的數會抵消,留下缺失的數。
時間複雜度:O(n) — 一次遍歷求和。
空間複雜度:O(1) — 只用兩個整數變數。
1. n = nums.size() 2. expected = n * (n + 1) / 2 3. actual = sum of all elements in nums 4. Return expected - actual
XOR 方法:xor_all = 0 XOR 1 XOR ... XOR n;xor_nums = 所有 nums 的 XOR;答案 = xor_all XOR xor_nums。避免超大 n 的潛在溢位。
排序 O(n log n):排序後找第一個 nums[i] != i 的索引。簡單但更慢。