【LeetCode】268.Missing Number解题报告
tags: Array
题目地址：https://leetcode.com/problems/missing-number/#/description 题目描述：
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.
题意：一个无序的序列，0到n之间只缺少一个数，找出缺的那个数。
Solutions:
解法一：
基本思想是使用异或运算。 我们都知道a ^ b ^ b = a，这意味着具有相同数字的两个xor操作将消除数字并显示原始数字。 在此解决方案中，我将XOR运算应用于数组的索引和值。 在一个没有丢失数字的完整数组中，索引和值应完全对应（nums [index] = index），所以在一个缺少的数组中，最后剩下的是缺少的数字。 下面是异或的运算法则
>
a ⊕ a = 0a ⊕ 0 = aa ⊕ b = b ⊕ aa ⊕b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c;d = a ⊕ b ⊕ c 可以推出 a = d ⊕ b ⊕ c.a ⊕ b ⊕ a = b. public class Solution { public int missingNumber(int[] nums) { int xor = 0, i = 0; for (i = 0; i < nums.length; i++) { xor = xor ^ i ^ nums[i]; } return xor ^ i; } }解法二：
因为只缺一个数，所有数几乎连续，求和容易。方法很巧！
public class Solution { public int missingNumber(int[] nums) { int sum = 0; for(int num: nums) sum += num; return (nums.length * (nums.length + 1) )/ 2 - sum; } }Date：2017年6月7日
