LeetCode 268. 丟失的數(shù)字
原題鏈接 ==11.6==
題目描述：
給定一個包含 [0, n] 中 n 個數(shù)的數(shù)組 nums 倍谜，找出 [0, n] 這個范圍內(nèi)沒有出現(xiàn)在數(shù)組中的那個數(shù)窃植。
要求：實現(xiàn)線性時間復(fù)雜度菱皆、僅使用額外常數(shù)空間的算法
代碼：
class Solution {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();
int res = n * (n + 1) / 2; // 不缺數(shù)的和
for (auto x : nums) res -= x;
return res; // 取差得res
}
};
前
個數(shù)的和是
，缺數(shù)字后的和為
，
時間復(fù)雜度： 只用求一次和徒溪，
空間復(fù)雜度：
