哈希算法篇——散落的秘密与精准的归宿，混沌中的秩序之美（下）

用户11379153

发布于 2025-11-05 15:55:15

1070

文章被收录于专栏：C++语法及相关算法详解C++语法及相关算法详解

前言

上篇我们介绍了哈希算法和哈希表的代码实现及其相关基本原理，本篇我们将结合具体题目，进一步深化对于哈希算法的掌握运用。

第一章：两数之和

1.1 题目链接：https://leetcode.cn/problems/two-sum/description/

1.2 题目分析：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
这两个整数不能为同一元素，但是值可以相同

1.3 思路讲解：

本题方法多样，且直接暴力遍历也可求解，此处主要讲解哈希算法求解该题。

如果我们可以事先将「数组内的元素」和「下标」绑定在⼀起存⼊「哈希表」中，然后直接在哈希表中查找每⼀个元素的 target - nums[i] ，就能快速的找到「⽬标和的下标」。 • 这⾥有⼀个⼩技巧，我们可以不⽤将元素全部放⼊到哈希表之后，再来⼆次遍历（因为要处理元素相同的情况）。⽽是在将元素放⼊到哈希表中的「同时」，直接来检查表中是否已经存在当前元素所对应的⽬标元素（即 target - nums[i] ）。如果它存在，那我们已经找到了对应解，并⽴即将其返回。⽆需将元素全部放⼊哈希表中，提⾼效率。 • 因为哈希表中查找元素的时间复杂度是 O(1) ，遍历⼀遍数组的时间复杂度为 O(N) ，因此可以将时间复杂度降到 O(N) 。

这是⼀个典型的「⽤空间交换时间」的⽅式。

1.4 代码实现：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> hash;//哈希
        for(int i=0;i<nums.size();i++)
        {
            int x=target-nums[i];
            if(hash.count(x))
            {
                return {hash[x],i};
            }
            else
            {
                hash[nums[i]]=i;
            }//存储下标
        }
        return {-1,-1};
        
    }
};

第二章：判断是否为字符重排

2.1 题目链接：https://leetcode.cn/problems/check-permutation-lcci/description/

2.2 题目分析：

给定两个字符串s和t，判断两字符串所含元素是否相等
所有元素均为小写字母

2.3 思路讲解：

是否为字符重排的核心即为两字符串所含元素是否相等

因此，我们可以通过哈希来记录字符串s的字符情况，之后再与字符串t对比
遍历过程中，如果相符则对应存储值减去1
当遍历完成时，哈希表存储的所有值如果都为0，说明满足字符重排，反之则不满足。

2.4 代码实现：

class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        int hash[26]={0};//模拟哈希
        if(s1.size()!=s2.size())
        {
            return false;
        }//如果字符数量不匹配直接返回false
        for(auto e:s1)
        {
            hash[e-'a']++;
        }//记录字符及其数量
        for(auto a:s2)
        {
            if(--hash[a-'a']<0)
            {
                return false;
            }
        }
        return true;
        
    }
};

第三章：存在重复元素|

3.1 题目链接：https://leetcode.cn/problems/contains-duplicate/description/

3.2 题目分析：

给定数组，如果所有元素各不相同，返回false
如果存在重复元素，则返回true

3.3 思路讲解：

我们可以采取哈希来记录每一个出现的元素，并在每一次记录时判断是否已经出现过
如果先前已经出现过，则返回true
如果遍历结束仍未返回，则返回false

3.4 代码实现：

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> hash;
        for(auto e:nums)
        {
            if(hash.count(e))
            {
                return true;
            }//如果该元素在此之前已出现过，证明出现重复元素
            else
            {
                hash.insert(e);
            }//反之正常插入即可

        }
        return false;
        
    }
};

第四章：存在重复元素||

4.1 题目链接：https://leetcode.cn/problems/contains-duplicate-ii/description/

4.2 题目分析：

给定数组和整数k，要求寻找数组内是否存在两个下标不同，但值相同的数，且要求两下标之差的绝对值小于等于K
若存在则返回true，反之，则返回false

4.3 思路讲解：

我们可以使⽤「哈希表」，令数组内的元素做 key 值，该元素所对应的下标做 val 值，将「数组元素」和「下标」绑定在⼀起，存⼊到「哈希表」中。
该题的另一核心在于两下标之差的绝对值小于等于k，此处可以采取贪心策略。

如果我们按照下标「从⼩到⼤」的顺序遍历数组，当遇到两个元素相同，并且⽐较它们的下标时，这两个下标⼀定是距离最近的，因为： • 如果当前判断符合条件直接返回 true ，⽆需继续往后查找。 • 如果不符合条件，那么前⼀个下标⼀定不可能与后续相同元素的下标匹配（因为下标在逐渐变⼤），那么我们可以⼤胆舍去前⼀个存储的下标，转⽽将其换成新的下标，继续匹配。

4.4 代码实现：

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int> hash;//哈希
        for(int i=0;i<nums.size();i++)
        {
            if(hash.count(nums[i]))
            {
                if(i-hash[nums[i]]<=k)
                {
                    return true;
                }
            }
            
                hash[nums[i]]=i;//更新下标
            
        }
        return false;
        
    }
};

第五章：字母异位词分组

5.1 题目链接：https://leetcode.cn/problems/group-anagrams/description/

5.2 题目分析：

异位词就是字符元素相等，但位置排列不同的字符串
该题要求将异位词分组合并，最终返回一个总的数组

5.3 思路讲解：

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> hash;//哈希表
        //排序遍历存储
        for(auto &e:strs)
        {
            string temp=e;
            sort(e.begin(),e.end());
            hash[e].push_back(temp);
        }
        //取出数据
        vector<vector<string>> ret;
        for(auto [x,y]:hash)
        {
            ret.push_back(y);
        }
        return ret;
        
    }
};