今日任務(wù)

● 哈希表理論基礎(chǔ)

● 242.有效的字母異位詞

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

● 202. 快樂數(shù)

● 1. 兩數(shù)之和

詳細(xì)布置

哈希表理論基礎(chǔ)

建議：大家要了解哈希表的內(nèi)部實(shí)現(xiàn)原理，哈希函數(shù)，哈希碰撞，以及常見哈希表的區(qū)別，數(shù)組，set 和map。

什么時(shí)候想到用哈希法，當(dāng)我們遇到了要快速判斷一個(gè)元素是否出現(xiàn)集合里的時(shí)候，就要考慮哈希法。 這句話很重要，大家在做哈希表題目都要思考這句話。

文章講解：https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

242.有效的字母異位詞

建議： 這道題目，大家可以感受到 數(shù)組 用來(lái)做哈希表 給我們帶來(lái)的遍歷之處。

題目鏈接/文章講解/視頻講解： https://programmercarl.com/0242.%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D.html

思路：數(shù)組其實(shí)就是一個(gè)簡(jiǎn)單哈希表，而且這道題目中字符串只有小寫字符，那么就可以定義一個(gè)數(shù)組，來(lái)記錄字符串s里字符出現(xiàn)的次數(shù)，需要定義一個(gè)多大的數(shù)組呢，定一個(gè)數(shù)組叫做record，大小為26 就可以了，初始化為0，因?yàn)樽址鸻到字符z的ASCII也是26個(gè)連續(xù)的數(shù)值。

class Solution {
public:
    bool isAnagram(string s, string t) {
        int hash[26] = {0};//定義一個(gè)哈希表來(lái)存儲(chǔ)兩個(gè)字符串中的字母
        for(int i = 0; i < s.size(); i++){
           hash[s[i] - 'a'] ++;//用0-25來(lái)代替a-z這些字母，數(shù)組里的值對(duì)應(yīng)該字母出現(xiàn)的次數(shù)
        }
        for(int i = 0; i < t.size(); i++){
           hash[t[i] - 'a'] --;//用0-25來(lái)代替a-z這些字母，字母出現(xiàn)幾次就減去幾
        }
        for(int i = 0; i < 26; i++){
 // record數(shù)組如果有的元素不為零0，說(shuō)明字符串s和t 一定是誰(shuí)多了字符或者誰(shuí)少了字符。
            if(hash[i] != 0){
                return false;
            }
        }
// record數(shù)組所有元素都為零0，說(shuō)明字符串s和t是字母異位詞
        return true;
    }    
};

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

建議：本題就開始考慮 什么時(shí)候用set 什么時(shí)候用數(shù)組，本題其實(shí)是使用set的好題，但是后來(lái)力扣改了題目描述和 測(cè)試用例，添加了 0 <= nums1[i], nums2[i] <= 1000 條件，所以使用數(shù)組也可以了，不過(guò)建議大家忽略這個(gè)條件。 嘗試去使用set。

題目鏈接/文章講解/視頻講解：https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html

哈希數(shù)據(jù)結(jié)構(gòu)：unordered_set

條件：輸出結(jié)果中的每個(gè)元素一定是唯一的，也就是說(shuō)輸出的結(jié)果的去重的， 同時(shí)可以不考慮輸出結(jié)果的順序

總結(jié)：創(chuàng)建哈希表，將nums1中出現(xiàn)的字母在哈希數(shù)組中做記錄；之后比較nums2中字母是否在表中出現(xiàn)

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result_set; 存放結(jié)果，之所以用set是為了給結(jié)果集去重
        unordered_set<int> nums1_set(nums1.begin(), nums1.end());
        for(int num : nums2){
? ? // 發(fā)現(xiàn)nums2的元素 在nums_set里又出現(xiàn)過(guò)
            if(nums1_set.find(num) != nums1_set.end()){
                result_set.insert(num);
            }
        }
        return vector<int>(result_set.begin() , result_set.end());
    }
};

202. 快樂數(shù)

建議：這道題目也是set的應(yīng)用，其實(shí)和上一題差不多，就是 套在快樂數(shù)一個(gè)殼子

題目鏈接/文章講解：https://programmercarl.com/0202.%E5%BF%AB%E4%B9%90%E6%95%B0.html

這道題目使用哈希法，來(lái)判斷這個(gè)sum是否重復(fù)出現(xiàn)，如果重復(fù)了就是return false， 否則一直找到sum為1為止

class Solution {
public:
    unordered_set<int>result;
    int getSum(int n){
        int sum = 0;
        while(n){
            sum += (n % 10) * (n % 10);
            n = n /10; 
        }
        return sum;
    }
    bool isHappy(int n){
       
        while(1){ 
            int sum = getSum(n);
            if(sum == 1){
                 return true;
            }
// 如果這個(gè)sum曾經(jīng)出現(xiàn)過(guò)，說(shuō)明已經(jīng)陷入了無(wú)限循環(huán)了，立刻return false
            if(result.find(sum) != result.end()){
                return false;
            }else{
                result.insert(sum);
            }
            n = sum;
        }
        
    }
     
};

1. 兩數(shù)之和

建議：本題雖然是 力扣第一題，但是還是挺難的，也是 代碼隨想錄中 數(shù)組，set之后，使用map解決哈希問(wèn)題的第一題。

建議大家先看視頻講解，然后嘗試自己寫代碼，在看文章講解，加深印象。

題目鏈接/文章講解/視頻講解：https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html

暴力法：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i = 0; i < nums.size(); i++){
            for(int j =i + 1; j < nums.size(); j++){
                if(nums[i]+nums[j] == target){
                    return{i, j};
                }
            }
        } 
        return {};
    }
};

本題需要一個(gè)集合來(lái)存放我們遍歷過(guò)的元素，然后在遍歷數(shù)組的時(shí)候去詢問(wèn)這個(gè)集合，某元素是否遍歷過(guò)，也就是 是否出現(xiàn)在這個(gè)集合。

那么我們就應(yīng)該想到使用哈希法了。

因?yàn)楸镜?，我們不僅要知道元素有沒有遍歷過(guò)，還有知道這個(gè)元素對(duì)應(yīng)的下標(biāo)，需要使用 key value結(jié)構(gòu)來(lái)存放，key來(lái)存元素，value來(lái)存下標(biāo)，那么使用map正合適。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-446625.html

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int>map;
        for(int i = 0; i < nums.size(); i++){
   // 遍歷當(dāng)前元素，并在map中尋找是否有匹配的key
            auto temp = map.find(target - nums[i]);
            if(temp != map.end()){
                return{temp -> second, i};
            }else{
  // 如果沒找到匹配對(duì)，就把訪問(wèn)過(guò)的元素和下標(biāo)加入到map中
                map.insert(pair<int,int>(nums[i], i));
            }
        } 
        return {};
    }
};