原題連接Missing Number

給定大小為n的數組，由0, 1, 2, …, n構成，其中缺少了某個值，找到它。要求時間復雜度是O(n)，空間復雜度是O(1)

雖然數組無序但是組成數組的元素整體有序而且每個元素是嚴格加一遞增（只有一個不是，假設這個值是m），考慮下面兩個和的表示形式

sum1 = 0 + 1 + 2 + ... + m-1 + m+1 + ... + n= 1 + 2 + ... + m-1 + m+1 + ... + n sum2 = 1 + 2 + ... + m-1 + m + m+1 + ... + n= (n * (n + 1)) / 2

其中，sum1是數組的和（缺少了m值），sum2是1到n的和，那么sum1和sum2實際上就是差了數組缺少的元素m，也就是通過sum2 - sum1即可計算出m的值

代碼實現如下

class Solution { public:int missingNumber(vector<int>& nums) {return (nums.size() * (nums.size() + 1)) / 2 - accumulate(nums.begin(), nums.end(), 0);} };

總結

以上是生活随笔為你收集整理的每天一道LeetCode-----找到由连续数字组成的数组中缺失的那个连续值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。