136. Single Number

原题链接：https://leetcode.com/problems/single-number/description/
这道题目刚看完半小时之后百思不得其解，然后本来打算看答案去了，无意间瞄了一眼“Related Topics”，发现里面提到两个词“Hash Table”和“Bit Manipulation”。其中第一个哈希表我是没想到怎么用来解决这个问题，但是第二个位运算却让我灵光一闪，对啊，就是异或运算喽！之所以能想到异或运算，是因为之前的一道面试题目也用到了它：http://www.cnblogs.com/optor/p/8271037.html
哈哈，那就愉快了写下了 Beats 100% 的答案了：

/**
 * Created by clearbug on 2018/2/26.
 */
public class Solution {

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.singleNumber(new int[]{1, 2, 2, 3, 4, 5, 8, 7, 8, 5, 4, 3, 1}));
    }

    public int singleNumber(int[] nums) {
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            res ^= nums[i];
        }
        return res;
    }
}

然后，我又顺便看了下官方答案。官方虽然提供了四种答案，但是前三种要么是时间复杂度超过了要求，要么是空间复杂度超过了要求，而第四种答案就是我想到的这种完美级别的答案了！