LeetCode 268 Missing Number（丟失的數字）

LeetCode 268 Missing Number（丟失的數字）

翻譯

給定一個包含從0,1,2...,n中取出來的互不相同的數字，從數組中找出一個丟失的數字。

例如，
給定nums = [0, 1, 3]
返回2。

備注:
你的算法應該運行在線性時間復雜度下。你可以只用常量空間復雜度來實現它嗎？

原文

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

分析

因為數組可以是非常非常大，其大小並不固定，所以哈希表應該是沒用了。

中間省略了一大段的思考過程，並且先去做了下面這道題，回到這道題的時候忽然有了思路。

LeetCode 319 Bulb Switcher（燈泡切換）（從規律中發現算法……）

比如說，從零到32146的數組中，丟失的數字是4687。

我們可以計算出從0到32146的所有數字的總和是：

expectedSum：516666585

我們還可以計算出從0到32146並丟掉4687的所有數字的總和是：

actualSum：516661898

對，沒錯，就是這樣……

代碼如下：

代碼

<code class=" hljs cpp">int missingNumber(vector<int>& nums) {
    int expectedSum = 0, actualSum = 0;
    for (int i = 1; i <= nums.size(); ++i) {
        expectedSum += i;
    }
    for (int i = 0; i < nums.size(); ++i) {
        actualSum += nums[i];
    }
    return expectedSum - actualSum;
}</int></code>