哈希表基础练习¶

约 3547 个字 370 行代码预计阅读时间 16 分钟

本篇介绍¶

哈希表是一个数据结构，一般用于处理判断一个元素是否存在，很少有题目单独考察哈希表，所以本篇的题目都是可以用哈希表解决，但有的可能不局限于用哈希表解决，通过下面的题目可以加深对哈希表使用的认识

力扣242.有效的字母异位词¶

力扣242.有效的字母异位词

问题描述：

Quote

给定两个字符串s和t，编写一个函数来判断t是否是s的字母异位词。

示例 1:

C++
输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

C++
输入: s = "rat", t = "car"
输出: false

思路分析：

所谓的字母异位词，就是一个只有字母构成的字符串中的所有字母重新打乱，并且每个字母只能使用一次构成的新字符串，这个新的字符串就是原字符串的字母异位词。在前面滑动窗口部分也有一个关于字母异位词的题目，两个地方的意思是一样的。根据字母异位词的意思，可以想到如果s中的字符都出现在t中，则证明s是t的字母异位词，如果s中存在一个字符不是t中的字符，则说明s不是t的字母异位词。根据提到的思路，可以考虑使用数组哈希表，只需要判断s中的字符是否全部存在于t中即可

注意，s中的字符除了可能比t中多了某些字母，有可能缺失t中的某些字母，此时s也不算t的字母异位词，这种情况下，s的长度一定小于t，所以如果s.size() < t.size()直接返回false即可

写法拓展：

在前面思路分析部分提到「如果s.size() < t.size()直接返回false即可」，如果s.size() > t.size()是否也可以直接返回false？答案是可以的（根据鸽巢原理），但是一定注意，如果s.size() == t.size()时可能是true也可能是false（例如s="cat", t = "car"）。根据大于和等于这两点，可以直接放在一起处理，因为如果是大于，则其中的某一些字母一定不存在于t中，同样相等也可能是某一个字母不存在于t中，所以既然都是某一个字母不存在于t中，就可以一起处理而没有必要分开处理

Note

上面提到的是写法上的不同，没有必要不代表不能写，取决于习惯

参考代码：

C++
class Solution242
{
public:
    bool isAnagram(string s, string t)
    {
        if (t.size() < s.size())
            return false;

        int hashA[27] = {0};
        int hashB[27] = {0};

        for (auto ch: s)
            hashA[ch - 'a']++;

        for (auto ch: t)
            hashB[ch - 'a']++;

        for (int i = 0; i < 26; i++)
            if (hashA[i] != hashB[i])
                return false;

        return true;
    }
};

力扣面试题01.04.回文排列¶

力扣面试题01.04.回文排列

问题描述：

Quote

给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。

回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。

回文串不一定是字典当中的单词。

示例1：

C++
输入："tactcoa"
输出：true（排列有"tacocat"、"atcocta"，等等）

思路分析：

本题乍一看以为需要用到暴力枚举出所有可能的回文串，实际上并不需要，因为如果一个字符串是回文串，肯定满足下面的条件：

「回文串」长度为偶数：所有不同字符的出现次数都为「偶数」
「回文串」长度为奇数：位于中点的字符出现「奇数」次，其余字符出现「偶数」次

根据上面的条件可以推出，如果出现奇数次数的字符不止一个，那么此时原字符串一定不能构成回文串，所以只需要判断字符出现次数是否满足出现奇数次数的字符小于等于1个

参考代码：

C++
class Solution0104
{
public:
    bool canPermutePalindrome(string s)
    {
        // 统计字符串中字符的个数
        int hash[128] = {0};
        // 判断是否满足出现奇数次的字符只出现1次或者0次
        int count = 0;
        // for (auto& ch : s) {
        //     hash[ch]++;
        //     if (hash[ch] % 2 == 0)
        //         count--;
        //     else
        //         count++;
        // }
        for_each(s.begin(), s.end(), [&](char ch)
        {
            hash[ch]++;
            if (hash[ch] % 2 == 0)
                count--;
            else
                count++;
        });

        return count <= 1;
    }
};

力扣383.赎金信¶

力扣383.赎金信

问题描述：

Quote

给你两个字符串：ransomNote和magazine，判断ransomNote能不能由magazine里面的字符构成。

如果可以，返回true；否则返回false。

magazine中的每个字符只能在ransomNote中使用一次。

示例 1：

C++
输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

C++
输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

C++
输入：ransomNote = "aa", magazine = "aab"
输出：true

思路分析：

本题和上一题非常类似，同样都是第一个字符串中不可以出现第二个字符串中没有的字母，但是本题需要注意，本题第二个字符串中的同一个字母可以在第一个字符串中使用多次，不同于上一题中的「只能使用一次」，根据这个不同，本题的思路在细节部分就会有不同，本题只需要满足第一个字符串中的某一个字母出现次数小于等于第二个字符串中对应的字母存在的个数，如果不满足则返回false

题目为什么叫“赎金信”

假设你是一个绑架犯，你想要写一封赎金信(ransomNote)，但是你只能使用某些杂志(magazine)上的字符来拼凑这封信。每个字符在杂志上只能使用一次。你的任务是判断你是否能够从杂志上拿到足够的字符来组成赎金信

参考代码：

C++
class Solution383
{
public:
    bool canConstruct(string ransomNote, string magazine)
    {
        int hash[26] = {0};
        for (auto ch: magazine)
            hash[ch - 'a']++;

        for (auto ch: ransomNote)
        {
            hash[ch - 'a']--;
            if (hash[ch - 'a'] < 0)
                return false;
        }

        return true;
    }
};

力扣面试题01.02.判定是否互为字符重排¶

力扣面试题01.02.判定是否互为字符重排

问题描述：

Quote

给定两个由小写字母组成的字符串s1和s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。

示例 1：

C++
输入: s1 = "abc", s2 = "bca"
输出: true 

示例 2：

C++
输入: s1 = "abc", s2 = "bad"
输出: false

思路分析：

本题思路和上题一致，只需要判断s2中出现的字符是否在s1中出现即可

思路拓展：

本题也可以通过is_permutation库函数协助解决

参考代码：

自己动手库函数

C++
class Solution0102_1
{
public:
    bool CheckPermutation(string s1, string s2)
    {
        // 长度不等一定不是重排
        if (s1.size() != s2.size())
            return false;

        int hash[26] = {0};
        // for (auto& ch : s2)
        //     hash[ch - 'a']++;
        for_each(s2.begin(), s2.end(), [&](char ch)
        {
            hash[ch - 'a']++;
        });

        for (auto &ch: s1)
            if (--hash[ch - 'a'] < 0)
                return false;


        return true;
    }
};

C++
class Solution0102_2
{
public:
    bool CheckPermutation(string s1, string s2) 
    {
        // 注意is_permutation库函数不能判断两个长度不同的集合
        if(s1.size() != s2.size())
            return false;
        return is_permutation(s1.begin(), s1.end(), s2.begin());
    }
};

力扣349.两个数组的交集¶

力扣349.两个数组的交集

问题描述：

Quote

给定两个数组nums1和nums2，返回它们的交集。输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。

示例 1：

C++
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

C++
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

思路分析：

交集：两个数组中都出现的元素

差集：两个数组中各自独有的元素

本题需要求交集，可以考虑使用set容器，首先将两个数组的元素都插入到set容器中，接着进行一一比较，当出现某一方较小，那么因为set容器插入元素是排序+去重，所以小的一方后面的数值都比该数值大，而对于另一方来说，因为当前数值比另一方当前数值小，所以另一方中的所有元素都不可能出现与小的数值有交集，此时向后移动小的一方的迭代器继续比较，如果出现相等，则说明是交集，以此类推，直到一方已经走到结尾

如果本题要求的是差集，则同样的思路，小的一方就是差集，需要注意其中一方走到结尾时，另一方的剩余内容也是差集结果的一部分

参考代码：

C++
class Solution349
{
public:
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2)
    {
        set<int> s(nums1.begin(), nums1.end());
        set<int> ret;

        for (auto num: nums2)
        {
            if (s.count(num))
            {
                ret.insert(num);
            }
        }

        return vector<int>(ret.begin(), ret.end());
    }
};

力扣350.两个数组的交集II¶

力扣350.两个数组的交集II

问题描述：

Quote

给你两个整数数组nums1和nums2，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

C++
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:

C++
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

思路分析：

本题要实现的目标与上一题基本一致，但是上一题并不要求元素在两个数组中都出现的次数一致，所以对于取交集思路见上题，本题主要考虑如何实现「元素在两个数组中都出现的次数一致」

在本题中，「元素在两个数组中都出现的次数一致」有两种情况：

交集元素在两个数组中出现的次数相同
交集元素在某一个数组中出现的次数小于另外一个数组中出现的次数

根据这两个情况可以考虑将两个数组的元素都放一个map中，map中存储的就是元素和其次数的映射，遍历时只需要遍历其中一个map，判断其元素是否在另一个map中出现就可以实现交集，如果存在，则根据其出现的次数插入到结果集中即可

参考代码：

C++
class Solution350
{
public:
    vector<int> intersect(vector<int> &nums1, vector<int> &nums2)
    {
        map<int, int> m1;
        map<int, int> m2;
        for (auto num: nums1)
            m1[num]++;

        for (auto num: nums2)
            m2[num]++;

        vector<int> ret;

        auto it = m1.begin();
        while (it != m1.end())
        {
            if (m2.find(it->first) != m2.end())
                if (m1[it->first] <= m2[it->first])
                    for (int i = 0; i < m1[it->first]; i++)
                        ret.push_back(it->first);
                else
                    for (int i = 0; i < m2[it->first]; i++)
                        ret.push_back(it->first);

            ++it;
        }

        return ret;
    }
};

力扣202.快乐数¶

力扣202.快乐数

问题描述：

Quote

编写一个算法来判断一个数n是不是快乐数。

「快乐数」定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和
重复这个过程直到这个数变为1，也可能是无限循环但始终变不到1
如果这个过程结果为1，那么这个数就是快乐数

如果n是快乐数就返回true；不是，则返回false

示例 1：

C++
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

C++
输入：n = 2
输出：false

思路分析：

解法1：哈希表

本题前面的思路就是简单的取出个位进行平方再相加如此往复的过程，但是其结果可能最后并不为1，如果不存在无限循环，那么本题只需要前面的思路加上一个判断是否等于1即可返回结果。但是本题存在无限循环，对于无限循环来说，本质就是某一个数值开始之后的数值会再次出现，如果出现这种情况，说明一定不存在最后结果等于1，在前面的计算过程之后加上判断是否之前出现过至少一次，如果出现，则证明出现了无限循环，直接返回false即可。这个过程中涉及到的「判断是否之前出现过至少一次」就可以使用哈希表来处理
解法2：双指针

关于双指针的具体思路将在双指针专题详细介绍，本次不做介绍

参考代码：

C++
class Solution202
{
public:
    bool isHappy(int n)
    {
        set<int> s;
        int temp = n;
        int sum = 0;
        while (temp != 1)
        {
            while (temp)
            {
                int r = temp % 10;
                temp /= 10;

                sum += r * r;
            }
            temp = sum;

            if (s.count(sum))
                return false;
            s.insert(sum);
            sum = 0;
        }

        return true;
    }
};

力扣1.两数之和¶

力扣1.两数之和

问题描述：

Quote

给定一个整数数组nums和一个整数目标值target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

C++
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

C++
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

C++
输入：nums = [3,3], target = 6
输出：[0,1]

思路分析：

解法1：暴力解法

本题的暴力解法就是枚举，找到两个元素使其和为target即可
解法2：哈希表

本题的哈希表解法需要使用逆向的思维，既然要求两个元素相加等于target，那么就是要求target-某一个元素后的结果是否在原数组中存在（即target-nums[i]是否等于nums[j]），判断一个元素是否存在就可以使用哈希表。具体做法是一层for循环遍历原数组，判断target-当前元素是否存在于哈希表中，如果存在就说明找到，否则就将该元素插入

需要注意，本题需要返回的是下标，所以需要使用map，存储的是元素和其下标的映射

思路拓展：

如果本题返回的不要求是下标而是元素，则本题还可以考虑使用双指针解决，但是双指针解法必须要对原数组进行排序，使其有单调性，双指针算法的时间复杂度就取决于排序的时间复杂度，一般都是\(O(log_{2}{N})\)，空间复杂度就是\(O(1)\)，而哈希表的思路就是空间换时间，时间复杂度和空间复杂度都是\(O(N)\)

Note

如果提前建立排序前的元素和对应下标的映射关系，则本题也可以考虑使用双指针解决

双指针具体思路如下：

排序数组
固定一个指针left指向数组的起始位置（从左向右移动），另外一个指针right指向数组终止位置（从右向左移动），通过一个变量sum记录这两个指针指向的元素之和，如果sum小于target则移动left，因为此时根据单调性，再移动right会使sum越来越小，left移动后再计算一次sum，如果大于，就移动right。直到和为target结束移动返回结果
如果left和right相遇还没遇到和为target，说明该数组不存在两个元素其和为target

双指针思路参考代码：

C++
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // 创建一个包含数值和原始索引的结构体
        struct NumIndex {
            int num;
            int index;
        };

        vector<NumIndex> numWithIndex;
        for (int i = 0; i < nums.size(); ++i) {
            numWithIndex.push_back({nums[i], i});
        }

        // 按数值排序
        sort(
            numWithIndex.begin(), numWithIndex.end(),
            [](const NumIndex& a, const NumIndex& b) { return a.num < b.num; });

        int left = 0;
        int right = numWithIndex.size() - 1;

        while (left < right) {
            int sum = numWithIndex[left].num + numWithIndex[right].num;

            if (sum == target) {
                // 根据题目要求指定返回元素还是下标
                return {numWithIndex[left].index, numWithIndex[right].index};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }

        return {}; // 如果没有找到，返回空数组
    }
};

在力扣上，也有类似于两数之和的题目：力扣LCR179.查找总价格为目标值的两个商品，这个题目就可以使用上面的双指针思路解决，下面是参考代码：

C++
class SolutionLCR179
{
public:
    vector<int> twoSum(vector<int> &price, int target)
    {
        for (int left = 0, right = price.size() - 1; left < right;)
        {
            if (price[left] + price[right] > target)
                right--;
            else if (price[left] + price[right] < target)
                left++;
            else
                return {price[left], price[right]};
        }

        return {};
    }
};

参考代码：

暴力解法哈希表

C++
class Solution1_1
{
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        int fast = 0;
        vector<int> ans;
        while(fast < nums.size())
        {
            int slow = fast + 1;
            while(slow < nums.size())
            {
                if(nums[slow] + nums[fast] == target)
                {
                    ans.push_back(slow);
                    ans.push_back(fast);
                    break;
                }
                slow++;
            }
            fast++;
        }

        return ans;
    }
};

C++
class Solution1_2
{
public:
    vector<int> twoSum(vector<int> &nums, int target)
    {
        vector<int> ret;
        // map存储下标和数值映射
        unordered_map<int, int> m;

        for (int i = 0; i < nums.size(); i++)
        {
            if (m.count(target - nums[i]))
            {
                return {i, m[target - nums[i]]};
            }
            m.insert({nums[i], i});
        }

        return {};
    }
};

力扣454.四数相加II¶

力扣454.四数相加II

问题描述：

Quote

给你四个整数数组nums1、nums2、nums3和nums4，数组长度都是n，请你计算有多少个元组(i, j, k, l)能满足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

C++
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

C++
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

思路分析：

本题和两数之和题目的思路是类似的，但是本题因为涉及到四个数组，所以考虑尽可能降低时间复杂度，四个数组遍历同时遍历则时间复杂度为\(O(N^4)\)，如果让一个数组先遍历，再遍历剩余三个数组，则时间复杂度为\(O(N^3)\)，如果两个为一组遍历，则时间复杂度为\(O(N^2)\)，所以考虑先遍历两个数组，计算出nums1[i] + nums2[j]，将a+b的结果存储到一个map中，接下来遍历剩下两个数组，计算出0-(nums3[k] + nums4[l])，如果其结果出现在map中，说明存在一个元组(i, j, k, l)使nums1[i] + nums2[j] + nums3[k] + nums4[l]的结果为0

参考代码：

C++
class Solution454
{
public:
    int fourSumCount(vector<int> &nums1, vector<int> &nums2, vector<int> &nums3, vector<int> &nums4)
    {
        // map处理和与次数的映射
        unordered_map<int, int> m;
        int count = 0;
        // 遍历前两个数组
        for (int i = 0; i < nums1.size(); i++)
        {
            for (int j = 0; j < nums2.size(); j++)
            {
                m[nums1[i] + nums2[j]]++;
            }
        }

        // 遍历后两个数组，如果获取到的值0-(c+d)==a+b，则说明出现过至少一次
        for (int i = 0; i < nums3.size(); i++)
        {
            for (int j = 0; j < nums4.size(); j++)
            {
                if (m.count(0 - nums3[i] - nums4[j]))
                {
                    count += m[0 - nums3[i] - nums4[j]];
                }
            }
        }

        return count;
    }
};