LeetCode 268. Missing Number （缺失的数字）

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?

题目标签：Array

　　题目给了我们一个nums array， array 里是从0 到n 的所有数字， 但是会缺失一个，让我们找出来，数字的排列不是有序的。

　　既然我们知道n，而且数字是从0 到 n 的，可以利用等差数列求和公式 0.5 * n * (n+1) 求出总和， 再遍历一次nums 算出实际的sum， 然后差值就是缺失的那个数字了。

Java Solution:

Runtime beats 49.88% 

完成日期：04/27/2017

关键词：Array

关键点：等差数列求和公式

 1 public class Solution 
 2 {
 3     public int missingNumber(int[] nums) 
 4     {
 5         int size = nums.length;
 6         
 7         int sum2 =  (size * (size + 1)) / 2;
 8         
 9         int sum1 = 0;
10         
11         for(int i=0; i < size; i++)
12             sum1 += nums[i];
13         
14         return (sum2 - sum1);
15     }
16 }

参考资料：N/A

LeetCode 算法题目列表 - LeetCode Algorithms Questions List

LeetCode 268. Missing Number （缺失的数字）

原文：http://www.cnblogs.com/jimmycheng/p/7497613.html