## Description

https://leetcode.com/problems/single-number/

Given a **non-empty** array of integers, every element appears *twice* except for one. Find that single one.

**Note:**

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

**Example 1:**

Input:[2,2,1]Output:1

**Example 2:**

Input:[4,1,2,1,2]Output:4

## Explanation

Use hash table to searching the elements that occur only once.

## Python Solution

```
class Solution:
def singleNumber(self, nums: List[int]) -> int:
count = {}
for num in nums:
if num in count:
count[num] += 1
else:
count[num] = 1
for key, value in count.items():
if value == 1:
return key
```

- Time complexity: O(N).
- Space complexity: O(N).

## One Thought to “LeetCode 136. Single Number”