這幾道【哈希表】相關(guān)的算法題，面試寫不出來就慘了！

airen89 2019-03-22

展開全文

散列表概念

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

更多有關(guān)散列表的詳細(xì)的介紹請戳這：動(dòng)畫：什么是散列表？

1. 兩數(shù)之和

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

題目描述

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

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

示例:

給定 nums = [2, 7, 11, 15], target = 9

因?yàn)?nbsp;nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

題目解析

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

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

每次遍歷時(shí)使用臨時(shí)變量 complement 用來保存目標(biāo)值與當(dāng)前值的差值
在此次遍歷中查找 record ，查看是否有與 complement 一致的值，如果查找成功則返回查找值的索引值與當(dāng)前變量的值i
如果未找到，則在 record 保存該元素與索引值 i

動(dòng)畫描述

代碼實(shí)現(xiàn)

// 1. Two Sum
// 時(shí)間復(fù)雜度：O(n)
// 空間復(fù)雜度：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. 無重復(fù)字符的最長子串

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

題目描述

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

題目解析

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

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

代碼實(shí)現(xiàn)

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0, left = -1, n = s.size();
        unordered_mapint, int> m;
        for (int i = 0; i <>
            if (m.count(s[i]) && m[s[i]] > left) {
                left = m[s[i]];  
            }
            m[s[i]] = i;
            res = max(res, i - left);            
        }
        return res;
    }
};

拓展

此題也可以使用滑動(dòng)窗口的概念來處理。

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

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

（1）如果當(dāng)前遍歷到的字符從未出現(xiàn)過，那么直接擴(kuò)大右邊界；
（2）如果當(dāng)前遍歷到的字符出現(xiàn)過，則縮小窗口（左邊索引向右移動(dòng)），然后繼續(xù)觀察當(dāng)前遍歷到的字符；
（3）重復(fù)（1）（2），直到左邊索引無法再移動(dòng)；
（4）維護(hù)一個(gè)結(jié)果 res，每次用出現(xiàn)過的窗口大小來更新結(jié)果 res ，最后返回 res 獲取結(jié)果。

代碼實(shí)現(xiàn)

// 3. Longest Substring Without Repeating Characters
// 滑動(dòng)窗口
// 時(shí)間復(fù)雜度: O(len(s))
// 空間復(fù)雜度: O(len(charset))
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int freq[256] = {0};
        int l = 0, r = -1; //滑動(dòng)窗口為s[l...r]
        int res = 0;
        // 整個(gè)循環(huán)從 l == 0; r == -1 這個(gè)空窗口開始
        // 到l == s.size(); r == s.size()-1 這個(gè)空窗口截止
        // 在每次循環(huán)里逐漸改變窗口, 維護(hù)freq, 并記錄當(dāng)前窗口中是否找到了一個(gè)新的最優(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 。

題目描述

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

題目解析

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

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

代碼實(shí)現(xiàn)

class Solution {
public:
    vectorvectorint>> threeSum(vectorint>& nums) {
        vectorvectorint>> res;
        sort(nums.begin(), nums.end());
        if (nums.empty() || nums.back() <>0 || nums.front() > 0) return {};
        for (int k = 0; k <>
            if (nums[k] > 0) break;
            if (k > 0 && nums[k] == nums[k - 1]) continue;
            int target = 0 - nums[k];
            int i = k + 1, j = nums.size() - 1;
            while (i <>
                if (nums[i] + nums[j] == target) {
                    res.push_back({nums[k], nums[i], nums[j]});
                    while (i <>1]) ++i;
                    while (i <>1]) --j;
                    ++i; --j;
                } else if (nums[i] + nums[j] <>
                else --j;
            }
        }
        return res;
    }
};

4. 重復(fù)的 DNA 序列

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

題目描述

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

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

題目解析

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

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

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

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

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

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

首先當(dāng)取出第十個(gè)字符時(shí)，將其存在哈希表里，和該字符串出現(xiàn)頻率映射，之后每向左移三位替換一個(gè)字符，查找新字符串在哈希表里出現(xiàn)次數(shù)，如果之前剛好出現(xiàn)過一次，則將當(dāng)前字符串存入返回值的數(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. 兩個(gè)數(shù)組的交集

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

題目描述

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

題目解析

容器類 set 的使用。

遍歷 num1，通過 set 容器 record 存儲 num1 的元素
遍歷 num2，在 record 中查找是否有相同的元素，如果有，用 set 容器 resultSet 進(jìn)行存儲
將 resultSet 轉(zhuǎn)換為 vector 類型

動(dòng)畫描述

代碼實(shí)現(xiàn)

// 時(shí)間復(fù)雜度: O(nlogn)
// 空間復(fù)雜度: O(n)
class Solution {
public:
    vectorint> intersection(vectorint>& nums1, vectorint>& nums2) {
        setint> record;
        for( int i = 0 ; i <>
            record.insert(nums1[i]);
        }
        setint> resultSet;
        for( int i = 0 ; i <>
            if(record.find(nums2[i]) != record.end()){
                resultSet.insert(nums2[i]);
            }
        }
        vectorint> resultVector;
        for(setint>::iterator iter = resultSet.begin(); iter != resultSet.end(); iter ++ ){
            resultVector.push_back(*iter);
        }

        return resultVector;
    }
};

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

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

題目描述

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

示例 1:

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

示例 2:

輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [4,9]

題目解析

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

遍歷 num1，通過 map 容器 record 存儲 num1 的元素與頻率；
遍歷 num2 ，在 record 中查找是否有相同的元素（該元素的存儲頻率大于 0 ），如果有，用 map 容器resultVector 進(jìn)行存儲，同時(shí)該元素的頻率減一。

動(dòng)畫描述

代碼實(shí)現(xiàn)

// 時(shí)間復(fù)雜度: O(nlogn)
// 空間復(fù)雜度: 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 對不同的點(diǎn)，“回旋鏢” 是由點(diǎn)表示的元組 (i, j, k) ，其中 i 和 j之間的距離和 i 和 k 之間的距離相等（需要考慮元組的順序）。

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

題目解析

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

遍歷所有的點(diǎn)，讓每個(gè)點(diǎn)作為一個(gè)錨點(diǎn)
然后再遍歷其他的點(diǎn)，統(tǒng)計(jì)和錨點(diǎn)距離相等的點(diǎn)有多少個(gè)
然后分別帶入 n(n-1) 計(jì)算結(jié)果并累加到 res 中

注意點(diǎn)：

如果有一個(gè)點(diǎn)a，還有兩個(gè)點(diǎn) b 和 c ，如果 ab 和 ac 之間的距離相等，那么就有兩種排列方法 abc 和 acb ；
如果有三個(gè)點(diǎn)b，c，d 都分別和 a 之間的距離相等，那么有六種排列方法，abc, acb, acd, adc, abd, adb；
如果有 n 個(gè)點(diǎn)和點(diǎn) a 距離相等，那么排列方式為 n(n-1)；
計(jì)算距離時(shí)不進(jìn)行開根運(yùn)算, 以保證精度；
只有當(dāng) n 大于等于 2 時(shí)，res 值才會(huì)真正增加，因?yàn)楫?dāng)n=1時(shí)，增加量為1 * ( 1 - 1 ) = 0 。

動(dòng)畫描述

代碼實(shí)現(xiàn)

// 時(shí)間復(fù)雜度: O(n^2)
// 空間復(fù)雜度: O(n)
class Solution {
public:
    int numberOfBoomerangs(vector<>int, int>>& points) {
        int res = 0;
        for( int i = 0 ; i <>
            // record中存儲 點(diǎn)i 到所有其他點(diǎn)的距離出現(xiàn)的頻次
            unordered_mapint, int> record;
            for(int j = 0 ; j <>
                if(j != i){
                    // 計(jì)算距離時(shí)不進(jìn)行開根運(yùn)算, 以保證精度
                    record[dis(points[i], points[j])] += 1;
                }
            }
            for(unordered_mapint, int>::iterator iter = record.begin() ; iter != record.end() ; iter ++){
                res += (iter->second) * (iter->second - 1);
            }
        }
        return res;
    }

private:
    int dis(const pairint,int> &pa, const pairint,int> &pb){
        return (pa.first - pb.first) * (pa.first - pb.first) +
               (pa.second - pb.second) * (pa.second - pb.second);
    }
};

8. 四數(shù)相加 II

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

題目描述

給定四個(gè)包含整數(shù)的數(shù)組列表 A , B , C , D ,計(jì)算有多少個(gè)元組 (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 之間，最終結(jié)果不會(huì)超過 2^31 - 1 。

題目解析

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

把 A 和 B 的兩兩之和都求出來，在哈希表中建立兩數(shù)之和與其出現(xiàn)次數(shù)之間的映射；
遍歷 C 和 D 中任意兩個(gè)數(shù)之和，只要看哈希表存不存在這兩數(shù)之和的相反數(shù)就行了。

動(dòng)畫描述

代碼實(shí)現(xiàn)

// 時(shí)間復(fù)雜度: O(n^2)
// 空間復(fù)雜度: 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;
    }
};

本站是提供個(gè)人知識管理的網(wǎng)絡(luò)存儲空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點(diǎn)擊一鍵舉報(bào)。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來自： airen89 > 《算法》

舉報(bào)/認(rèn)領(lǐng)