Given an array of integers, every element appears twice except for one. Find that single one.

大意为给定一个整数数组，数组中除了一个元素只有一个外，其他元素均出现两次，找出一个的这个元素

思路

最初想法将数组每个数扫描进一个集合，没扫进一个元素判断集合中是否已存在，存在则删除集合中的相应元素，否则将元素添加进集合，最后集合中剩下的那个元素则为单个元素

代码

public int singleNumber(int[] nums) {
    List<Integer> list = new ArrayList<>();
    for (int i : nums) {
        if (!list.contains(i))
            list.add(i);
        else
            list.remove((Integer) i);
    }
    return list.remove(0);
}

优化

上面的方法虽然能通过测试，但是数据量一大所需内存会很大，运行时间也很慢，所以根据异或运算的规律做出了优化方案

public int planB(int[] nums) {
    int single = 0;
    for (int i : nums) {
        single ^= i;
    }
    return single;
}