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?
Runtime: 36ms
1 class Solution { 2 public: 3 int missingNumber(vector<int>& nums) { 4 if(nums.size() == 0) return 0; 5 6 int sumOrigin = 0, sumCurrent = 0; 7 for(int i = 0; i < nums.size(); i++){ 8 sumCurrent += nums[i]; 9 sumOrigin += i + 1; 10 } 11 return sumOrigin - sumCurrent; 12 } 13 };
原文：http://www.cnblogs.com/amazingzoe/p/4929128.html