# Week 8: Hash Tables

### What is a hash table?

A **hash table** (aka **hash map**) is a data structure which stores data as **key-value** pairs. The **keys** of a hash table are *hashed* to produce a unique value, which is then used to store the data in the table (thus, the keys of a hash table must be unique). This allows for very fast lookup and retrieval of the data, regardless of the size of the table.

### What is a set?

A **set** (aka **hash set**) is a collection of unique elements. It is similar to a hash table, but only stores keys (no values).

### Hash table example:

This is a hash table that uses strings as keys and stores an array of strings as values.

Key | Values |
---|---|

animals | rabbit, dog |

fruits | apple, watermelon, pineapple |

continents | Asia, Europe, Africa |

```
// Create a hashtable
Hashtable<String, String[]> hashtable = new Hashtable<>();
// Add elements to the hashtable
String[] animals = {"rabbit", "dog"};
hashtable.put("animals", animals);
String[] fruits = {"apple", "watermelon", "pineapple"};
hashtable.put("fruits", fruits);
String[] continents = {"Asia", "Europe", "Africa"};
hashtable.put("continents", continents);
// Get a value from the hashtable given a key
hashtable.get("animals")[0]; // returns "rabbit"
hashtable.get("vegetables"); // returns null
// Check if a key exists in the hashtable
hashTable.containsKey("animals"); // returns true
// Check if a value exists in the hashtable
hashTable.contains(animals); // returns true
hashtable.isEmpty(); // returns false
hashtable.size(); // returns 3
```

### 1) Count Number of Unique Elements in Array

Given an integer array, return the number of unique integers in the array.

**Example 1:**

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

**Example 2:**

```
Input: [1,2,3,4,5]
Output: 5
```

### 2) Check if Number Has Equal Digit Count and Digit Value

You are given a 0-indexed string `num`

of length `n`

consisting of digits.

Return `true`

if for every index `i`

in the range `0 <= i < n`

, the digit `i`

occurs `num[i]`

times in `num`

, otherwise return `false`

.

**Example 1:**

```
Input: num = "1210"
Output: true
Explanation:
num[0] = '1'. The digit 0 occurs once in num.
num[1] = '2'. The digit 1 occurs twice in num.
num[2] = '1'. The digit 2 occurs once in num.
num[3] = '0'. The digit 3 occurs zero times in num.
The condition holds true for every index in "1210", so return true.
```

**Example 2:**

```
Input: num = "030"
Output: false
Explanation:
num[0] = '0'. The digit 0 should occur zero times, but actually occurs twice in num.
num[1] = '3'. The digit 1 should occur three times, but actually occurs zero times in num.
num[2] = '0'. The digit 2 occurs zero times in num.
The indices 0 and 1 both violate the condition, so return false.
```

*Constraints:*

`n == num.length`

`1 <= n <= 10`

`num`

consists of digits

### 3) Two Sum

Given an array of integers `nums`

and an integer `target`

, return indices of the two numbers such that they add up to `target`

.

**Example 1:**

```
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation:
Since nums[0] + nums[1] == 9, we return [0, 1].
```

**Example 2:**

```
Input: nums = [3,2,4], target = 6
Output: [1,2]
Explanation:
Since nums[1] + nums[2] == 6, we return [1, 2].
```

**Example 3:**

```
Input: nums = [3,3], target = 6
Output: [0,1]
Explanation:
Since nums[0] + nums[1] == 6, we return [0, 1].
```

### 4) Pairs of Songs With Total Durations Divisible by 60

You are given a list of songs where the `ith`

song has a duration of `time[i]`

seconds.

Return the number of pairs of songs for which their total duration in seconds is divisible by `60`

. Formally, we want the number of indices `i`

, `j`

such that `i < j`

with `(time[i] + time[j]) % 60 == 0`

.

**Example 1:**

```
Input: time = [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60
```

**Example 2:**

```
Input: time = [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.
```

*Constraints:*

`1 <= time.length <= 6 * 10^4`

`1 <= time[i] <= 500`

### 5) Repeated DNA Sequences

The DNA sequence is composed of a series of nucleotides abbreviated as `'A'`

, `'C'`

, `'G'`

, and `'T'`

.

For example, `"ACGAATTCCG"`

is a DNA sequence.
When studying DNA, it is useful to identify repeated sequences within the DNA.

Given a string `s`

that represents a DNA sequence, return all the `10`

-letter-long sequences (substrings) that occur more than once in a DNA molecule. You may return the answer in any order.

**Example 1:**

```
Input: s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output: ["AAAAACCCCC","CCCCCAAAAA"]
```

**Example 2:**

```
Input: s = "AAAAAAAAAAAAA"
Output: ["AAAAAAAAAA"]
```

*Constraints:*

`1 <= s.length <= 10^5`

`s[i]`

is either`'A'`

,`'C'`

,`'G'`

, or`'T'`

.