2019-01-28 第四天 (#217, #219)

因为#217不能傻乎乎地像#299那样自制Hash Table了（因为涉及到hashing值的算法），这里也算是对C++ STL自带的两种Hash Table数据结构unordered_set和unordered_map做一个梳理。

unordered_set
这个是最简单的Hash Table，只能知道对应key值在table中是否存在，也就是说key值没有对应的value。
Geeksforgeeks 上的例子：

// C++ program to demonstrate various function of unordered_set 
#include <bits/stdc++.h> 
using namespace std; 

int main() 
{ 
    // declaring set for storing string data-type 
    unordered_set<string> stringSet; 

    // inserting various string, same string will be stored 
    // once in set 
    stringSet.insert("code"); 
    stringSet.insert("in"); 
    stringSet.insert("c++"); 
    stringSet.insert("is"); 
    stringSet.insert("fast"); 

    string key = "slow"; 

    //   find returns end iterator if key is not found, 
    // else it returns iterator to that key 
    if (stringSet.find(key) == stringSet.end()) 
        cout << key << " not found\n\n"; 
    else
        cout << "Found " << key << endl << endl; 

    key = "c++"; 
    if (stringSet.find(key) == stringSet.end()) 
        cout << key << " not found\n"; 
    else
        cout << "Found " << key << endl; 

    // now iterating over whole set and printing its 
    // content 
    cout << "\nAll elements : "; 
    unordered_set<string> :: iterator itr; 
    for (itr = stringSet.begin(); itr != stringSet.end(); itr++) 
        cout << (*itr) << endl; 
} 

最重要的几个操作：

unorder_set<template> hash_set
hash_set.insert()
hash_set.find(key)
hash_set.end()

unordered_map
这个是带key和value的Hash Map，使用方法和unordered_set大体一致。[Geeksforgeeks]上的例子：https://www.geeksforgeeks.org/unordered_map-in-cpp-stl/

// C++ program to demonstrate functionality of unordered_map 
#include <iostream> 
#include <unordered_map> 
using namespace std; 

int main() 
{ 
    // Declaring umap to be of <string, double> type 
    // key will be of string type and mapped value will 
    // be of double type 
    unordered_map<string, double> umap; 

    // inserting values by using [] operator 
    umap["PI"] = 3.14; 
    umap["root2"] = 1.414; 
    umap["root3"] = 1.732; 
    umap["log10"] = 2.302; 
    umap["loge"] = 1.0; 

    // inserting value by insert function 
    umap.insert(make_pair("e", 2.718)); 

    string key = "PI"; 

    // If key not found in map iterator to end is returned 
    if (umap.find(key) == umap.end()) 
        cout << key << " not found\n\n"; 

    // If key found then iterator to that key is returned 
    else
        cout << "Found " << key << "\n\n"; 

    key = "lambda"; 
    if (umap.find(key) == umap.end()) 
        cout << key << " not found\n"; 
    else
        cout << "Found " << key << endl; 

    // iterating over all value of umap 
    unordered_map<string, double>:: iterator itr; 
    cout << "\nAll Elements : \n"; 
    for (itr = umap.begin(); itr != umap.end(); itr++) 
    { 
        // itr works as a pointer to pair<string, double> 
        // type itr->first stores the key part and 
        // itr->second stroes the value part 
        cout << itr->first << " " << itr->second << endl; 
    } 
} 

区别只是可以用umap["PI"] = 3.14这样的形式插入key和value，同时注意用insert()函数的时候要用make_pair来插入。

#217 Contains Duplicate

题目地址：https://leetcode.com/problems/contains-duplicate/

可以说是unordered_setconstructor最简单直观的应用，一行解决。

class Solution {
  public:
    bool containsDuplicate(vector<int>& nums) {
        return unordered_set<int>(nums.begin(), nums.end()).size() < nums.size();
    }
};

#219 Contains Duplicate II

题目地址：https://leetcode.com/problems/contains-duplicate-ii/
这题就要用到unordered_map了，把条件分为两种情况：没找到&找到了但是坐标（value）相差不到k vs. 找到了且满足条件。前一种情况更新坐标，后一种情况直接返回true即可。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> hash_map;
        for(int i = 0; i < nums.size(); i++){
            if(hash_map.find(nums.at(i)) == hash_map.end() || 
              i - hash_map[nums.at(i)] > k)
                hash_map[nums.at(i)] = i;
            else 
                return true;
        }
        
        return false;
    }
};