散列表概念

散列表（Hash table，也叫哈希表），是根據(jù)鍵（Key）而直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結構。也就是說，它通過計算一個關于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個位置來訪問記錄，這加快了查找速度。這個映射函數(shù)稱做散列函數(shù)，存放記錄的數(shù)組稱做散列表。

更多有關散列表的詳細的介紹請戳這：動畫：什么是散列表？

1. 兩數(shù)之和

題目來源于 LeetCode 上第 1 號問題： Two Sum。

題目描述

給定一個整數(shù)數(shù)組 nums 和一個目標值 target，請你在該數(shù)組中找出和為目標值的那 兩個 整數(shù)，并返回他們的數(shù)組下標。

你可以假設每種輸入只會對應一個答案。但是，你不能重復利用這個數(shù)組中同樣的元素。

示例:

題目解析

使用散列表來解決該問題。

首先設置一個 map 容器 record 用來記錄元素的值與索引，然后遍歷數(shù)組 nums 。

• 每次遍歷時使用臨時變量 complement 用來保存目標值與當前值的差值

• 在此次遍歷中查找 record ，查看是否有與 complement 一致的值，如果查找成功則返回查找值的索引值與當前變量的值i

• 如果未找到，則在 record 保存該元素與索引值 i

動畫描述

代碼實現(xiàn)

// 1. Two Sum
// 時間復雜度：O(n)
// 空間復雜度：O(n)
class Solution {
public:
    vectorint> twoSum(vectorint>& nums, int target) {
        unordered_mapint,int> record;
        for(int i = 0 ; i <>
            int complement = target - nums[i];
            if(record.find(complement) != record.end()){
                int res[] = {i, record[complement]};
                return vectorint>(res, res + 2);
            }
            record[nums[i]] = i;
        }
    }
};

2. 無重復字符的最長子串

題目來源于 LeetCode 上第 3 號問題：  Longest Substring Without Repeating Characters 。

題目描述

給定一個字符串，請你找出其中不含有重復字符的 最長子串 的長度。

題目解析

建立一個 HashMap ，建立每個字符和其最后出現(xiàn)位置之間的映射，然后再定義兩個變量 res 和 left ，其中 res 用來記錄最長無重復子串的長度，left 指向該無重復子串左邊的起始位置的前一個，一開始由于是前一個，所以在初始化時就是 -1。

接下來遍歷整個字符串，對于每一個遍歷到的字符，如果該字符已經(jīng)在 HashMap 中存在了，并且如果其映射值大于 left 的話，那么更新 left 為當前映射值，然后映射值更新為當前坐標 i，這樣保證了 left 始終為當前邊界的前一個位置，然后計算窗口長度的時候，直接用 i-left 即可，用來更新結果 res 。

代碼實現(xiàn)

拓展

此題也可以使用滑動窗口的概念來處理。

建立一個 256 位大小的整型數(shù)組 freg ，用來建立字符和其出現(xiàn)位置之間的映射。

維護一個滑動窗口，窗口內(nèi)的都是沒有重復的字符，去盡可能的擴大窗口的大小，窗口不停的向右滑動。

• （1）如果當前遍歷到的字符從未出現(xiàn)過，那么直接擴大右邊界；

• （2）如果當前遍歷到的字符出現(xiàn)過，則縮小窗口（左邊索引向右移動），然后繼續(xù)觀察當前遍歷到的字符；

• （3）重復（1）（2），直到左邊索引無法再移動；

• （4）維護一個結果 res，每次用出現(xiàn)過的窗口大小來更新結果 res ，最后返回 res 獲取結果。

代碼實現(xiàn)

// 3. Longest Substring Without Repeating Characters
// 滑動窗口
// 時間復雜度: O(len(s))
// 空間復雜度: O(len(charset))
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int freq[256] = {0};
        int l = 0, r = -1; //滑動窗口為s[l...r]
        int res = 0;
        // 整個循環(huán)從 l == 0; r == -1 這個空窗口開始
        // 到l == s.size(); r == s.size()-1 這個空窗口截止
        // 在每次循環(huán)里逐漸改變窗口, 維護freq, 并記錄當前窗口中是否找到了一個新的最優(yōu)值
        while(l <>
            if(r + 1 <>1]] == 0){
                r++;
                freq[s[r]]++;
            }else {   //r已經(jīng)到頭 || freq[s[r+1]] == 1
                freq[s[l]]--;
                l++;
            }
            res = max(res, r-l+1);
        }
        return res;
    }
};

3. 三數(shù)之和

題目來源于 LeetCode 上第 15 號問題： 3Sum 。

題目描述

給定一個包含 n 個整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？找出所有滿足條件且不重復的三元組。

題目解析

題目需要我們找出三個數(shù)且和為 0 ，那么除了三個數(shù)全是 0 的情況之外，肯定會有負數(shù)和正數(shù)，所以一開始可以先選擇一個數(shù)，然后再去找另外兩個數(shù)，這樣只要找到兩個數(shù)且和為第一個選擇的數(shù)的相反數(shù)就行了。也就是說需要枚舉 a 和 b ，將 c 的存入 map 即可。

需要注意的是返回的結果中，不能有有重復的結果。這樣的代碼時間復雜度是 O(n^2)。在這里可以先將原數(shù)組進行排序，然后再遍歷排序后的數(shù)組，這樣就可以使用雙指針以線性時間復雜度來遍歷所有滿足題意的兩個數(shù)組合。

代碼實現(xiàn)

4. 重復的 DNA 序列

題目來源于 LeetCode 上第 187 號問題：  Repeated DNA Sequences 。

題目描述

所有 DNA 由一系列縮寫為 A，C，G 和 T 的核苷酸組成，例如：“ACGAATTCCG”。在研究 DNA 時，識別 DNA 中的重復序列有時會對研究非常有幫助。

編寫一個函數(shù)來查找 DNA 分子中所有出現(xiàn)超過一次的 10 個字母長的序列（子串）。

題目解析

首先，先將  A , C , G , T 的 ASCII 碼用二進制來表示：

A: 0100 0001　　C: 0100 0011　　G: 0100 0111　　T: 0101 0100

通過觀察發(fā)現(xiàn)每個字符的后三位都不相同，因此可以用末尾的三位來區(qū)分這四個字符。

題目要求是查找 10 個字母長的序列，這里我們將每個字符用三位來區(qū)分的話，10 個字符就需要 30 位 ，在32位機上也 OK 。

為了提取出后 30 位，需要使用 mask ，取值為 0x7ffffff（二進制表示含有 27 個 1） ，先用此 mask 可取出整個序列的后 27 位，然后再向左平移三位可取出 10 個字母長的序列 （ 30 位）。

為了保存子串的頻率，這里使用哈希表。

首先當取出第十個字符時，將其存在哈希表里，和該字符串出現(xiàn)頻率映射，之后每向左移三位替換一個字符，查找新字符串在哈希表里出現(xiàn)次數(shù)，如果之前剛好出現(xiàn)過一次，則將當前字符串存入返回值的數(shù)組并將其出現(xiàn)次數(shù)加一，如果從未出現(xiàn)過，則將其映射到 1。

解題代碼

class Solution {
public:
    vectorstring> findRepeatedDnaSequences(string s) {
        vectorstring> res;
        if (s.size() <>10) return res;
        int mask = 0x7ffffff, cur = 0;
        unordered_mapint, int> m;
        for (int i = 0; i <>9; ++i) {
            cur = (cur <>3) | (s[i] & 7);
        }
        for (int i = 9; i <>
            cur = ((cur & mask) <>3) | (s[i] & 7);
            if (m.count(cur)) {
                if (m[cur] == 1) res.push_back(s.substr(i - 9, 10));
                ++m[cur]; 
            } else {
                m[cur] = 1;
            }
        }
        return res;
    }
};

5. 兩個數(shù)組的交集

題目來源于 LeetCode 上第 349 號問題：  Intersection of Two Arrays。

題目描述

給定兩個數(shù)組，編寫一個函數(shù)來計算它們的交集。

題目解析

容器類 set 的使用。

• 遍歷 num1，通過 set 容器 record 存儲 num1 的元素

• 遍歷 num2，在 record 中查找是否有相同的元素，如果有，用 set 容器 resultSet 進行存儲

• 將 resultSet 轉(zhuǎn)換為 vector 類型

動畫描述

代碼實現(xiàn)

6. 兩個數(shù)組的交集 II

題目來源于 LeetCode 上第 350 號問題：  Intersection of Two Arrays II。

題目描述

給定兩個數(shù)組，編寫一個函數(shù)來計算它們的交集。

示例 1:

輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]

示例 2:

題目解析

與上題 兩個數(shù)組的交集 類似。只不過這里使用的是 map 。

• 遍歷 num1，通過 map 容器 record 存儲 num1 的元素與頻率；

• 遍歷 num2 ，在 record 中查找是否有相同的元素（該元素的存儲頻率大于 0 ），如果有，用 map 容器resultVector 進行存儲，同時該元素的頻率減一。

動畫描述

代碼實現(xiàn)

// 時間復雜度: O(nlogn)
// 空間復雜度: O(n)
class Solution {
public:
    vectorint> intersect(vectorint>& nums1, vectorint>& nums2) {
        mapint, int> record;
        for(int i = 0 ; i <>
             record[nums1[i]] += 1;
        }
        vectorint> resultVector;
        for(int i = 0 ; i <>
            if(record[nums2[i]] > 0){
                resultVector.push_back(nums2[i]);
                record[nums2[i]] --;
            }
        }
        return resultVector;
    }
};

7. 回旋鏢的數(shù)量

題目來源于 LeetCode 上第 447 號問題：  Number of Boomerangs 。

題目描述

給定平面上 n 對不同的點，“回旋鏢” 是由點表示的元組 (i, j, k) ，其中 i 和 j之間的距離和 i 和 k 之間的距離相等（需要考慮元組的順序）。

找到所有回旋鏢的數(shù)量。你可以假設 n 最大為 500，所有點的坐標在閉區(qū)間 [-10000, 10000] 中。

題目解析

n 最大為 500，可以使用時間復雜度為 O(n^2)的算法。

• 遍歷所有的點，讓每個點作為一個錨點

• 然后再遍歷其他的點，統(tǒng)計和錨點距離相等的點有多少個

• 然后分別帶入 n(n-1) 計算結果并累加到 res 中

注意點：

• 如果有一個點a，還有兩個點 b 和 c ，如果 ab 和 ac 之間的距離相等，那么就有兩種排列方法 abc 和 acb ；

• 如果有三個點b，c，d 都分別和 a 之間的距離相等，那么有六種排列方法，abc, acb, acd, adc, abd, adb；

• 如果有 n 個點和點 a 距離相等，那么排列方式為 n(n-1)；

• 計算距離時不進行開根運算, 以保證精度；

• 只有當 n 大于等于 2 時，res 值才會真正增加，因為當n=1時，增加量為1 * ( 1 - 1 ) = 0 。

動畫描述

代碼實現(xiàn)

8. 四數(shù)相加 II

題目來源于 LeetCode 上第 454 號問題： 4Sum II 。

題目描述

給定四個包含整數(shù)的數(shù)組列表 A , B , C , D ,計算有多少個元組 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

為了使問題簡單化，所有的 A, B, C, D 具有相同的長度 N，且 0 ≤ N ≤ 500 。所有整數(shù)的范圍在 -2^28 到 2^28- 1 之間，最終結果不會超過 2^31 - 1 。

題目解析

與 Two Sum 極其類似，使用哈希表來解決問題。

• 把 A 和 B 的兩兩之和都求出來，在哈希表中建立兩數(shù)之和與其出現(xiàn)次數(shù)之間的映射；

• 遍歷 C 和 D 中任意兩個數(shù)之和，只要看哈希表存不存在這兩數(shù)之和的相反數(shù)就行了。

動畫描述

代碼實現(xiàn)

// 時間復雜度: O(n^2)
// 空間復雜度: O(n^2)
class Solution {
public:
    int fourSumCount(vectorint>& A, vectorint>& B, vectorint>& C, vectorint>& D) {
        unordered_mapint,int> hashtable;
        for(int i = 0 ; i <>
            for(int j = 0 ; j <>
                 hashtable[A[i]+B[j]] += 1;
            }
        }
        int res = 0;
        for(int i = 0 ; i <>
            for(int j = 0 ; j <>
                if(hashtable.find(-C[i]-D[j]) != hashtable.end()){
                    res += hashtable[-C[i]-D[j]];
                }
            }
        }
        return res;
    }
};