[数据结构与算法]剑指offer 56-2仅仅一个数x出现一次，其余出现三次，找x

题目描述

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：
输入：nums = [3,4,3,3]
输出：4
示例 2：
输入：nums = [9,1,7,9,7,9,7]
输出：1

##题目分析：
可以用两种方法。

1. 位运算
2. 求和法。这种要注意求完和有可能会很大，超过int范围，所以要将和的变量定义为long，最后再强制转为int。

/*
class Solution {
    public int singleNumber(int[] nums) {
        //方法一：利用位运算
        //将每个元素的二进制按位分别进行相加，得到的每一位的1的个数之后2中情况：3的倍数或者3的倍数+1，那么这个+1就是目标值带来的
        int res = 0;
        for(int i = 0; i < 32; i++){
            int cnt = 0;
            for(int j = 0; j < nums.length; j++){
                if((nums[j] >> i & 1) == 1){//右移nums[j]的二进制，与1，即可该位是否等于1，右移就是把右边的一位挤掉，所以每次可以将当前位变为最右边的，从而与1相与。
                    cnt++;
                }
            }
            if(cnt % 3 != 0){//该位与目标值有关
                res = res | 1 << i;
            }
        }
        return res;
    }
}
*/

class Solution {
    public int singleNumber(int[] nums) {
        //用求和的方法，需要哈希表的辅助
        //先求所有数的和
        //易错点：有个样例求完和值会很大，会超出int范围，所以定义为long
        long addAllNum = 0;
        long addHashSet = 0;
        HashSet<Integer> set = new HashSet<>();
        for(int num : nums){
            addAllNum += num;
            if(!set.contains(num)){
                set.add(num);
                addHashSet += num;
            }
        }
        //addHashSet * 3 - addAllNum = 2*目标值
        int res = (int)((addHashSet * 3 - addAllNum) / 2);
        return res;
    }
}