(LeetCode OJ)Missing Number【268】

(LeetCode OJ)Missing Number【268】

 

268. Missing Number

My Submissions Question Total Accepted: 31740 Total Submissions: 83547 Difficulty: Medium

 

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?

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

 

Subscribe to see which companies asked this question

Hide Tags Array Math Bit Manipulation Hide Similar Problems (H) First Missing Positive (M) Single Number (H) Find the Duplicate Number  

//思路首先：
//我真服了這個題，題意理解錯了，我還以為是干嘛呢！
//後來才明白原來是隨機從0到size()選取了一些數，其中有一個丟失了，草
//別人的算法：數學推出，0到size()的總和減去當前數組和sum

class Solution {
public:
    int missingNumber(vector& nums) {
        int sum = 0;  
        for(int num: nums)
            sum += num;  
        int n = nums.size();  
        return (n * (n + 1))/ 2 - sum;  
    }
};