1. 哈希表

????哈希表通過哈希函數(shù)使得關(guān)鍵字與數(shù)值之間產(chǎn)生映射關(guān)系。

????最簡單的哈希表就是數(shù)組，關(guān)鍵字是index（索引），數(shù)值為數(shù)組在此索引內(nèi)的值。這種方法優(yōu)點是編碼十分的簡單，但是占用空間大，空間利用率低。而且當多個數(shù)值需要映射到同一個關(guān)鍵字時會產(chǎn)生沖突，例如在離散數(shù)學中關(guān)于0-100內(nèi)%3的整數(shù)集。由此需要有解決沖突的方法：開放定址法、拉鏈法。

2.??有效的字母異位詞 242

????輸入：字符串A，字符串B

????輸出：是否A中的每個字符在B中都出現(xiàn)了相同次數(shù)

????解題目思想：遍歷A建立一個map<字符,出現(xiàn)次數(shù)>，關(guān)鍵字為A中出現(xiàn)的字符進行累加操作；遍歷B將關(guān)鍵字為B中出現(xiàn)的字符進行累減操作。最終遍歷map若其中有不為0的數(shù)值則不滿足條件。

????時空復雜度：O(n)

3.?兩個數(shù)組的交集 349

????輸入：數(shù)組A，B

????輸出：數(shù)組C（是AB的交集）

????解題思想：使用set之關(guān)注元素是否存在過而不用在意個數(shù)，將A中出現(xiàn)過的元素插入set，遍歷B若B中的元素在set中存在則加入數(shù)組C

????時空復雜度：O(n)

4. 快樂數(shù) 202

????快樂數(shù)一點都不快樂。

? 「快樂數(shù)」 定義為：

? ? 對于一個正整數(shù)，每一次將該數(shù)替換為它每個位置上的數(shù)字的平方和。

? ? 然后重復這個過程直到這個數(shù)變?yōu)?1，也可能是 無限循環(huán) 但始終變不到 1。

? ? 如果這個過程 結(jié)果為 1，那么這個數(shù)就是快樂數(shù)。

????無線循環(huán)在本題中一定會產(chǎn)生結(jié)果的冗余。

5. 兩數(shù)之和

????輸入：一組數(shù)組

????輸出：一對索引對

????解題思路：在遍歷數(shù)組的過程中將無法匹配的元素封裝入map<元素值,索引>中，若在數(shù)組遍歷完成之前出現(xiàn)了匹對成功的元素，將其索引對返回。

????