哈希入門題目解決(C++) 必看

學完本文，你需要自己解決：

創(chuàng)新互聯公司專注于企業(yè)營銷型網站、網站重做改版、莒縣網站定制設計、自適應品牌網站建設、H5場景定制、成都做商城網站、集團公司官網建設、外貿網站建設、高端網站制作、響應式網頁設計等建站業(yè)務，價格優(yōu)惠性價比高，為莒縣等各大城市提供網站開發(fā)制作服務。

1. 兩數之和 - 力扣（LeetCode）

242. 有效的字母異位詞 - 力扣（LeetCode）

349. 兩個數組的交集 - 力扣（LeetCode）

202. 快樂數 - 力扣（LeetCode）

454. 四數相加 II - 力扣（LeetCode）

最近剛開始看STL源碼剖析，才知道啥叫一入C++深似海，當然扯遠了，hash類不僅面試常考，而且我認為難度是不次于RBTree和AVL等數據結構的。 至于hash類的實現，讀者感興趣的可以看STL源碼剖析，本文是對std::unordered_set和unordered_map的應用，只是為了教授讀者如何使用常見的接口。

hash： 查詢和刪除是 o(1)的復雜度 記住這一點就可以了

常見的接口一定要掌握的，第一重要的就是[]。這個運算符對于hash有特殊的意義。官方文檔寫：

Ifkmatches the key of an element in the container, the function returns a reference to its mapped value.

Ifkdoes not match the key of any element in the container, the function inserts a new element with that key and returns a reference to its mapped value. Notice that this always increases the container size by one, even if no mapped value is assigned to the element (the element is constructed using its default constructor).

總結[]的三大功能就是 ： 1：找(如果存在) 2.插入(key不存在) 3 改

為了避免抽象我用一段簡單代碼解釋下：

unordered_mapmymap;
	mymap["jack"] = 1;
	mymap["lisa"] = 1; //插入
	mymap["james"] = 0;

	int status = mymap["jack"]; //找
	cout<< status<< endl;

	mymap["james"] = 1; //改
	cout<< mymap["james"]<< endl;

另一個常見接口是find，具體內容大家看文檔就可以了，用來查找的，有一點我給新手讀者強調下，find找不到會返回end的迭代器，這點要注意，我們經常要利用。

簡單模式

242. 有效的字母異位詞 - 力扣（LeetCode）

這道題其實很好的反映了哈希思想，其實哈希的本質就是映射，這道題我們沒有必要用stl的hash解決，我就用數組了，每一個字母我們映射到對應的位置，一個加一個減，最后數組含有非0就是false。

class Solution {
public:
    bool isAnagram(string s, string t) {
    vectorres(26, 0);

    for (auto e: s)
    {
        res[e - 'a']++;
    }

    for (auto e : t)
    {
        res[e- 'a']--;
    }

    for (auto e : res)
    {
        if (e != 0)
            return false;
    }

    return true;
    }
};

349. 兩個數組的交集 - 力扣（LeetCode）

這道題我們想一下，找交集，可以用兩層for，挨個去比對。我們有沒有更好的辦法？ 其實就是哈希，我們先用set去重以后，遍歷一個數組，然后用find接口去找，因為在哈希中find是o(1)的對吧，這樣就一層for就解決了，比較簡單，直接上代碼了。

class Solution {
public:
    vectorintersection(vector& nums1, vector& nums2) {
    unordered_setres;
    unordered_setset(nums1.begin(), nums1.end());

    

    for (auto e : nums2)
    {
        if (set.find(e) != set.end())
        {
            res.insert(e);
        }
    }
    return vector(res.begin(), res.end());
    }
};

這里我唯一要說的就是，很多新手很納悶這個find咋等于end去了啊，注意，我再次強調，文檔一定好好看，find找不到的時候會返回end的迭代器。 所以這句代碼的意思就是我們在set里面找到了e，所以加入到結果集。

202. 快樂數 - 力扣（LeetCode）

這個題也比較有意思。題目說有可能會無限循環(huán)也到不了1，很多讀者理解不了這啥意思。 我舉個例子啊，比如2， 下一步是4， 16， 37， 58，89，145，42，18，65，61，37. 到這我們發(fā)現了一個重要的問題，凡是這個不是快樂數的啊，我們算著算著一定會倒回去，不信的你可以自己再舉例試試啊。 所以很簡單，我們直接開一個set，用find找是吧。

bool isHappy(int n) {
    unordered_setres;

    while (1)
    {
        int sum1 = sum(n);
        if (sum1 == 1)
            return true;
        else 
        {
            if (res.find(sum1) != res.end())
            {
                return false;
            }
            else
                res.insert(sum1);
        }

        n = sum1;
    }

這里怎么求每位數的平方就是sum函數我就不寫了，讀者應該都會。

幾個數字的和

這里這兩個題比之前的有些難度還是。

1. 兩數之和 - 力扣（LeetCode）

這個題算倆數的和，咋算呢，其實本質我還是利用這個find，但是以前咱們都是find這個數對吧，現在應該find啥啊，其實就是target-我們當前這個數，倆數是不是就能湊出來了啊。

class Solution {
public:
    vectortwoSum(vector& nums, int target) {
        std::unordered_mapmap; 
        for(int i = 0; i< nums.size(); i++) {
            // 遍歷，并在map中尋找是否有匹配的key
            auto iter = map.find(target - nums[i]); 
            if(iter != map.end()) {
                return {iter->second, i};
            }
            // 如果沒找到，就把訪問過的元素和下標加入到map中
            map.insert(pair(nums[i], i)); 
        }
        return {};
    }
};

本題需要我們輸出索引，所以我們用map，pair(數字，索引)來表示，最后返回的也是iterator的second。還有大家做OJ的時候啊，有的題目要求必須有返回值的，讀者想我們在接口里面肯定就返回了啊不可能到外面來，這個只需要在外面處理一下，寫個空就好了。

454. 四數相加 II - 力扣（LeetCode）

其實幾個數相加的這種問題啊，框架是差不多，但是細節(jié)實現起來就個然不同。這道題老實說一開始我也沒有太好辦法，你直接四個肯定超時。但是看了一下給的數據大小，n是小于200的，想了想優(yōu)化下，兩個數組分成一組，然后去湊。 a+b+c+d == 0， 我ab湊好了以后， 去找 0 -(a+b) 就是(c+d)。還有就是我們找到了應該＋幾也是個問題，其實應該加的是key對應的value啊，千萬不能加1，因為你想你a+b比如等于5，可能是1和4， 2和3， 很多種情況是不是啊，所以都要加和。

class Solution {
public:
    int fourSumCount(vector& nums1, vector& nums2, vector& nums3, vector& nums4) {
    unordered_mapmap1;


    for(auto e: nums1)
    {
        for(auto x: nums2)
        {
            map1[e + x]++; //我這里說一下范圍for的用法，新手搞不清里面這個e是啥意思，到底是索引還是數字
        }//范圍for里面的元素全部是迭代器啊，我強調一下，就是你用范圍for是無法找索引的，因為他是用迭代器遍歷的
    }
    int count = 0;
    for (auto e: nums3)
    {
        for(auto x: nums4)
        {
            int target = 0 - (e + x);
            if (map1.find(target) != map1.end())
            {
                count += map1[target]; 
            }
        }
    }
    return count;
    }
};

哈希表的應用和玩法還是很多的。等我啃啃書，過段時間再來講解下一些比較難的題。感謝觀看。

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

標題名稱：哈希入門題目解決(C++)必看-創(chuàng)新互聯
URL分享：http://www.chinadenli.net/article34/ccchpe.html

成都網站建設公司_創(chuàng)新互聯，為您提供動態(tài)網站、建站公司、網站營銷、網站導航、響應式網站、虛擬主機

廣告

聲明：本網站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯