目錄

理論基礎(chǔ)

242.有效的字母異位詞

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

202.快樂數(shù)

1.兩數(shù)之和

理論基礎(chǔ)

哈希表用來判斷一個元素是否出現(xiàn)在集合里（判斷一個元素是否出現(xiàn)過）。犧牲空間換時間，會使用到額外的空間。

又稱散列表，key-value,根據(jù)key值來訪問

（數(shù)組就是簡單的哈希表，但是數(shù)組的大小不是無限開辟的）

哈希函數(shù)：

????????

hashCode將其他數(shù)據(jù)格式轉(zhuǎn)為數(shù)值。使用取模tableSize來避免hashCode得到的數(shù)值大于了哈希表的大小。

哈希碰撞：

? ? ? ? 學(xué)生的數(shù)量大于哈希表大小。大于1個，映射到了同一個索引位置。

? ? ? ? 拉鏈法：發(fā)生沖突的元素存儲在這個位置的鏈表中

????????

????????線性探測法：沖突元素相應(yīng)存在后面的空位置上。數(shù)據(jù)規(guī)模dataSize需大于tableSize，否則沒有空位。

????????

三種哈希結(jié)構(gòu)：

? ? ? ? （表格中除第二行寫全外，其他兩行與第一行對比后只在不同處寫）

? ? ? ? （對于map來說，有序重復(fù)數(shù)值修改指的都是key，value不管）

? ? ? ? （考慮順序（根據(jù)題目）：unordered_set -> set -> multiset）（首先考慮unordered，它的查詢和刪除效率最優(yōu)，如果還需要有序，就用set，如果要求不僅有序還要有重復(fù)數(shù)據(jù)，就用multi）

? ? ? ? ? ?紅黑樹是一種平衡二叉搜索樹，故key值有序，但key不可修改，只能增刪

• 數(shù)組：大小有限制，如果元素很少，哈希值太大會造成內(nèi)存空間的浪費
• set集合：只有key，適用于哈希值很大或者哈希值比較少，特別分散，跨度非常大的情況
• map映射：有key和value

242.有效的字母異位詞

解決辦法：

? ? ? ? 1. 暴力解法：兩個for循環(huán)嵌套，定義一個布爾變量，用來實時判斷是否找到相同字符串，若找到則true,未找到則false,最后根據(jù)該布爾變量的值來return。

class Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.length() != t.length()) {
            return false;
        }
        for (int i = 0; i < s.length(); i++) {
            bool find = false;
            for (int j = 0; j < t.length(); j++) {
                if (s[i] == t[j]) {
                    t.erase(j, 1);
                    find =true;
                    break;
                }
            }
            if (!find) {
                return false;
            }
        }
        return true;
    }
};

? ? ? ??時間復(fù)雜度O(n^2）

? ? ? ?2.? 哈希表：

? ? ? ? 判斷相同字符是否出現(xiàn)過，用哈希表。（判斷某個元素是否出現(xiàn)在集合里）

????????這里巧妙利用字符a到字符z的ASCII碼值是26個連續(xù)的數(shù)值（數(shù)據(jù)量小，數(shù)組），將字符映射到數(shù)組也就是哈希表的索引下標上，并借助減去'a'，不需要記住字符a的ASCII碼值，讓其對應(yīng)上數(shù)組從0開始的索引，即定義一個大小為26的數(shù)組。s中對應(yīng)字母+1，t中在數(shù)組對應(yīng)字母-1，若最后數(shù)組所有元素均為0，則s,t中字母元素及對應(yīng)個數(shù)相同。（數(shù)組來記錄每個字符出現(xiàn)的次數(shù)）

? ? ? ? 都是a-z的小寫字母，數(shù)值小且可控，用數(shù)組來做映射就可以了。

 Solution {
public:
    bool isAnagram(string s, string t) {
        if (s.size() != t.size()) { // 長度不同則直接不可能為字母異位詞
            return false;
        }
        int hash[26] = {0}; // 在函數(shù)內(nèi)部聲明數(shù)組時，顯式的對元素初始化
        for (int i = 0; i < s.size(); i++) {
            hash[s[i] - 'a']++; // 相對數(shù)值，不需要記住字符a確切的ASCII碼值
            hash[t[i] - 'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (hash[i] != 0) {
                return false;
            }
        }
        return true;

    }
};

????????時間復(fù)雜度O(n)

????????空間復(fù)雜度O(1)

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

解決辦法：

? ? ? ? 需判斷第二個數(shù)組里的元素是否出現(xiàn)在第一個數(shù)組去重后的集合里，故用哈希表。（判斷某個元素是否出現(xiàn)在集合里）

? ? ? ? 1. 數(shù)組解法（和上一題類似）（元素題目給了限制，故數(shù)組大小不超過1000，0<=nums[1],nums[2]<=1000）

? ? ? ? 使用unordered_set來定義result，實現(xiàn)自動降重（題目要求了輸出結(jié)果中每個元素唯一，不考慮輸出結(jié)果的順序）

? ? ? ? return?vector<int>(result_set.begin(), result_set.end());最后把set轉(zhuǎn)化成vector

? ? ? ? hash直接初始化為一個固定大小數(shù)組

? ? ? ? 增強for循環(huán)更簡潔

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set;
        int hash[1005] = {0}; //稍大一點即可

        // for (int i = 0; i < nums1.size(); i++) {
        //     hash[nums1[i]] = 1;
        // }
        // for (int i = 0; i < nums2.size(); i++) {
        //     if (hash[nums2[i]] == 1) {
        //         result.insert(nums2[i]);
        //     } 
        // }

        for (int num : nums1) { // 增強for循環(huán)
            hash[num] = 1;
        }
        for (int num : nums2) {
            if (hash[num] == 1) {
                result_set.insert(num); // 會自動降重
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

? ? ? ? 時間復(fù)雜度O(n + m)

? ? ? ? 空間復(fù)雜度O(n) (result_set最壞情況與輸入數(shù)組成線性關(guān)系）

? ? ? ? 2. set解法 （題目未限制數(shù)值的大小，可能會非常大；哈希值比較少、特別分散、跨度非常大。最好也用set，畢竟此時用數(shù)組就會造成極大的空間浪費）（但如果限制了數(shù)值大小，就最好用數(shù)組了，因為set占用空間會比數(shù)組大，同時速度也比數(shù)組慢，set把數(shù)值映射到key上都要做hash計算）

????????find(num)函數(shù)返回一個迭代器，指向nums_set集合中找到的元素，如果沒有找到，則返回nums_set.end()，即集合的尾后迭代器。

????????nums_set（hash）初始化為nums1，大小就不是固定的，如果數(shù)值非常大，也不會出現(xiàn)像數(shù)組那樣一堆空間被浪費情況

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set;
        unordered_set<int> nums_set(nums1.begin(), nums1.end()); // 初始化為nums1中的元素
        for (int num : nums2) {
            if (nums_set.find(num) != nums_set.end()) { // nums2的元素是否在nums_set里
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
    }
};

????????時間復(fù)雜度O(n + m) nums1儲存到numsz-set為n，find為1，nums2遍歷為m，k(k<=n)是最后要把set轉(zhuǎn)成vector

????????空間復(fù)雜度O(n)

202.快樂數(shù)

解決辦法：

? ? ? ? 題提到會無限循環(huán)，即在求和過程中sum重復(fù)出現(xiàn)，故需判斷sum是否重復(fù)出現(xiàn)，故用哈希表。（快速判斷一個元素是否出現(xiàn)在集合里）

? ? ? ?注意如何取數(shù)值各個位來進行單數(shù)操作。

class Solution {
public:
    // 取數(shù)值各個位上的單數(shù)之和
    int getSum(int n) {
        int sum = 0;
        while(n) {
            sum += (n % 10) * (n % 10);
            n /= 10;
        }
        return sum;
    }

    bool isHappy(int n) {
        // 判斷重復(fù)出現(xiàn)否，故用unordered_set自動降重
        unordered_set<int> nums_set;
        // while(1)無限循環(huán)
        while (1) {
            int sum = getSum(n);
            if (sum == 1) {
                return true;
            }
            // 若sum已出現(xiàn)過，則進入無限循環(huán)了
            if (nums_set.find(sum) != nums_set.end()) {
                return false;
            } else {
                nums_set.insert(sum);
            }
            // n又等于新的sum值
            n = sum; 
        }

    }
};

????????時間復(fù)雜度O(logn)

????????空間復(fù)雜度O(logn)

（主要是getSum函數(shù)，對n的每一位進行一次操作，總共有l(wèi)og10(n)+1位；find查找和insert操作都是O(1)）

1.兩數(shù)之和

解決辦法：

? ? ? ? 本題解題思路為每遍歷一個數(shù)后，查看前面（單獨存放在一個集合）是否有遍歷到與本數(shù)相加能得到target的數(shù)，如果有，就找到了匹配對，如果沒有，就把當(dāng)前遍歷數(shù)添加到集合里。（注意這里符合的兩個整數(shù)并不一定是相鄰的）

• 為什么用哈希表：要判斷前面是否有遍歷到符合要求的數(shù)。（判斷某個元素是否出現(xiàn)過）
• 為什么用map：本題除了要找到該元素，還要找到該元素的下標。map映射有key和value
• 本題的map作用：用來存放已經(jīng)遍歷過的元素，進而判斷是否已遍歷過符合要求的數(shù)
• key,value分別是什么：這里要找的是某個元素是否出現(xiàn)過，那么就用key來保存元素(map就是能在短時間內(nèi)找到key是否出現(xiàn)過）,value來保存下標。
• unordered_map：本題不需要有序，且同一個元素不能重復(fù)出現(xiàn)

????????注意map的一些語法以及返回兩個下標的寫法

????????auto：自動推導(dǎo)變量類型，不然這里寫成unordered_map<int, int>

????????pair<int, int>：模板類，表示包含兩個int類型元素的有序?qū)Γ@里就是將元素和對應(yīng)下標打包成有序?qū)Σ⒎祷??？捎糜诖鎯蓚€不同類型的值，擁有公共成員變量first和second

? ? ? ? {iter->second, i}：花括號{}進行列表初始化，這個向量會被創(chuàng)建并直接作為函數(shù)的返回值。iter->second指的是map中差值元素對應(yīng)的下標，i是當(dāng)前元素的下標

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        for (int i = 0; i < nums.size(); i++) {
            int s = target - nums[i]; // 要查找的前面是否出現(xiàn)過的數(shù)
            auto iter = map.find(s);
            // 遍歷當(dāng)前元素，并在map中查找是否有匹配的key
            if (iter != map.end()) {
                return {iter->second, i};
            } else {
                map.insert(pair<int, int>(nums[i], i));
            }
        }
        return {};
    }
};

????????時間復(fù)雜度O(n)

????????空間復(fù)雜度O(n)

由于相關(guān)知識缺乏，基本上沒啥思路，故就不寫第一思路和解決狀態(tài)了，主要就直接寫解決辦法了。文章來源地址http://www.zghlxwxcb.cn/news/detail-831531.html

到了這里，關(guān)于力扣 | 哈希表1 | 242.有效的字母異位詞，349.兩個數(shù)組的交集，202.快樂數(shù)，1.兩數(shù)之和的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！