Hash table 雜湊表,一個 key-value 的資料結構,能根據給予的 key 以 O(1) 時間找出 value
Hash table 會有一個 hash function,其 function 計算出鍵值,並將 value 映射到表中一個位置,透過這樣的儲存與取值方式加速。
而在 C++ 中,又有 4個容易搞混的東西:map, set, unordered_map, unordered_set
其中 map 與 set 是透過紅黑樹建構而成,unordered_map 與 unordered_set 才是 hash table。
而 unordered_set 只有 key,並沒有 value。
例題:217. Contains Duplicate
直接使用 leetcode easy 的題目結束這一回合
Given an array of integers, find if the array contains any duplicates.
Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
Example 1:
Input: [1,2,3,1]
Output: true
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
// 建立一個 key 跟 value 皆為 int 的 hash table
unordered_map<int, int> m;
// 將數組加入 hash table
for (auto v : nums)
++m[v];
// 如果 second(value) 超過 1 個,則表示存在 "Duplicate"
for (auto p : m) {
if (p.second > 1) {
return true;
}
}
return false;
}
};