# 只出现一次的数字 III
---

- 剑指 Offer 56 - I. 数组中数字出现的次数

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 

找出只出现一次的那两个元素。

示例 :

输入: [1,2,1,3,2,5]

输出: [3,5]

注意：

结果输出的顺序并不重要，对于上面的例子，[5, 3] 也是正确答案。

进阶：

你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

:::success

// map特性， key唯一

func singleNumber(nums []int) []int {
	maps := make(map[int]int, 0)
	result := make([]int, 0)
	count := 1

	for i := 0; i < len(nums); i++ {
		_, ok := maps[nums[i]]
		if !ok {
			maps[nums[i]] = count
		} else {
			maps[nums[i]] = count + 1
		}
	}

	for key, value := range maps {
		if value == 1 {
			result = append(result, key)
		}
	}

	return result
}
 
// 位运算

func singleNumber(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}

	if len(nums) == 2 && nums[0] != nums[1] {
		return nums
	}

	/*
		[a, c, c, d, b, d] -> c ^ c ^ d ^ d ^ a ^ b -> a ^ b
		a ^ a = 0
		a ^ 0 = a
		因为 a, b 只出现了一次, 剩余元素都出现两次，遍历异或整个数组，只剩下 a^b且不为0
	 */



	resp := make([]int, 0)

	result := nums[0]

	for i := 1; i < len(nums); i++ {
		result ^= nums[i]
	}

	diff := result & -result

	a := 0

	// 我们通过 result & (-result) 保留 result 最右边的 1，这个 1 要么来自 a，要么来自 b
	for _, val := range nums {
		if diff & val != 0 {
			a ^= val
		}
	}

	resp = append(resp, a)
	b := result ^ a // b = a ^ b ^ a
	resp = append(resp, b)

	return resp
}

:::

###### tags: `LeeCode`