理论基础

哈希表就是一个map，key：value的数据结构。 一般哈希表都是用来快速判断一个元素是否出现集合里。

常见的三种哈希结构

当我们想使用哈希法来解决问题的时候，我们一般会选择如下三种数据结构。

数组
set （集合）
map(映射) 在C++中，set 和 map 分别提供以下三种数据结构，其底层实现以及优劣如下表所示：

常用的相关函数

赋值

用一个 unordered_set 来建立一个 vector<int> 的哈希。

vector<int> nums1
unordered_set<int> set1(nums1.begin(),nums1.end());

或者

for(auto v: nums1)
{
	set1.insert(v);
}

242. 有效的字母异位词

给定两个字符串 _s_ 和 _t_ ，编写一个函数来判断 _t_ 是否是 _s_ 的字母异位词。 **注意：**若 _s_ 和 _t_ 中每个字符出现的次数都相同，则称 _s_ 和 _t_ 互为字母异位词。

分析

建立一个map，遍历s中的元素建立哈希映射，一个元素计数+1；遍历t中元素则-1；最后遍历这个map，要求整个哈希表的value全是0，否则就不是有效的。 最开始可以写一个判断两个字符串的长度是否相等的if来减少整体的复杂度。

解答

bool isAnagram(string s, string t) {  
    // 首先排除s和t长度不相等的情况  
    if (s.length() != t.length()) {  
        return false;  
    }  
    // 将字符串s用unordered_set建立hash  
    unordered_map<char, int> map;  
    for(auto c : s)  
    {  
        map[c]+=1;  
    }  
    for(auto c : t)  
    {  
        map[c]-=1;  
    }  
    // 遍历map，如果有值不为0，说明s和t不相等  
    for(auto it = map.begin(); it != map.end(); it++)  
    {  
        if (it->second != 0)  
        {  
            return false;  
        }  
    }  
    return true;  
}

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

分析

这道题目不能按照顺序逐个遍历每个子字符两两之间的关系，那样代码会很难写，需要逐步枚举每一种组合，查询是否其在已经建立的map中，否则则增加到表中。不如将每一个字符按照顺序重新排一下作为key，然后该字符串本身作为value。最终可以只进行一次遍历就将整个字符组都排序好。

解答

string sortString(string s) {  
    sort(s.begin(), s.end());  
    return s;  
}  
vector<vector<string>> groupAnagrams(vector<string>& strs) {  
    unordered_map<string, vector<string>> map;  
    for(int i = 0; i < strs.size(); i++)  
    {  
        string temp = sortString(strs[i]);  
        map[temp].push_back(strs[i]);  
    }  
    vector<vector<string>> res;  
    for (auto it = map.begin(); it != map.end(); it++)  
    {  
        res.push_back(it->second);  
    }  
    return res;  
}

438. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。 示例 1: 输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

分析

[!NOTE] 正确但会超时的做法以sort之后的p为key，遍历字符串s，每次取和p一样大的子串，同样sort一下，如果和key一样，就把索引添加到map中。

class Solution {
public:
    string sortString(string s) {
        sort(s.begin(), s.end());
        return s;
    }
    vector<int> findAnagrams(string s, string p) {
        if (s.size() < p.size())
            return {};        
        unordered_map<string, vector<int>> map;
        string key = sortString(p);
        for (int i = 0; i < s.size() - p.size()+1; i++) {
            string tmp = s.substr(i, p.size());
            tmp = sortString(tmp);
            if(tmp == key)
                map[tmp].push_back(i);
        }
        return map[key];
    }
};

虽然能过但复杂度依旧很高的做法

bool isAnagram(string& sub, unordered_map<char, int> map) {  
    for(auto c: sub)  
    {  
        if(map[c] == 0)  
            return false;  
        map[c]--;  
    }  
    return true;  
}  
  
vector<int> findAnagrams(string s, string p) {  
    if (s.size() < p.size())  
        return {};  
    unordered_map<char, int> map;  
    for (int i = 0; i < p.size(); i++) {  
        map[p[i]]++;  
    }  
    vector<int> res;  
    for (int i = 0; i < s.size() - p.size()+1; ) {  
        string sub = s.substr(i, p.size());  
        if (isAnagram(sub, map))  
        {  
            res.push_back(i);  
            while (s[i] == s[i+p.size()])  
            {  
                res.push_back(++i);  
            }  
            i=i+2;  
        }  
        else  
            i++;  
    }  
    return res;  
}

解答

! TODO:

使用滑动窗口法会更加简单

383. 赎金信

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

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

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

分析

一个map记录magezine中的字符。遍历ransomNote的每一个字母，看map能不能够组成这张赎金信，if (map[c] == 0)，说明某个字母在magezine中不存在，或者该字母不够了。那就false。

解答

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<char, int> map;
        for (auto c: magazine)
        {
            map[c]++;
        }
        for (auto c: ransomNote)
        {
            if (map[c] == 0) // 因为magazine中的字母是不能重复使用的，所以不能用find。//map[c] == 0 要么就是没有这个字母，要么就是这个字母之前用过，现在不够用了，那也是不行。
            {
                return false;
            }
            map[c]--;
        }
        return true;
    }
};

349. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。 示例 1： 输入： nums1 = [1,2,2,1], nums2 = [2,2] 输出： [2]

分析

先用一个unordered_set (key不能重复) 建立nums1 数组的哈希
然后遍历nums2的元素，去上面的set中找，找得到得就添加到result中，由于输出的result需要是去重的，所以result也用一个unordered_set

解答

vector<int> intersection2(vector<int>& nums1, vector<int>& nums2) {  
    //只需要使用一个 unordered_set 来存nums1，再用一个 unordered_set 来存去重的results  
    // 上面这样做的好处是可以节省由于建立hash表所引入的时间  
    unordered_set<int> set1(nums1.begin(),nums1.end());  
    unordered_set<int> results;  
    // 遍历 nums2 中的元素  
    for(auto num : nums2)  
    {  
        if(set1.find(num)!=set1.end())  
        {  
            results.insert(num);  
        }
    }  
    return vector<int>(results.begin(),results.end());  
}

350. 两个数组的交集 II

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

示例 2: 输入： nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出： [4,9]

分析

和349. 两个数组的交集不同的是，这道题目的输出要求不去重。而且需要知道每个元素出现的次数，所以应该使用map数据结构。
使用两个map分别建立nums1和nums2的哈希
迭代器it遍历某一个哈希表，在另外一个哈希表中find，如果找到，则比较二者中元素个数更少的那个，将该元素copy n份放入result。

解答

class Solution {  
public:  
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {  
        // 分别建立哈希表  
        unordered_map<int, int> map1, map2;  
        for (int i = 0; i < nums1.size(); i++) {  
            map1[nums1[i]]++;  
        }  
        for (int i = 0; i < nums2.size(); i++) {  
            map2[nums2[i]]++;  
        }  
        vector<int> res;  
        for(auto it = map1.begin(); it != map1.end(); it++)  
        {  
            if(map2.find(it->first) != map2.end())  
            {  
                int count = min(it->second, map2[it->first]);  
                for(int i = 0; i < count; i++)  
                {  
                    res.push_back(it->first);  
                }  
            }  
        }  
        return res;  
    }  
};

202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」 定义为：

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

分析

写个函数，输入某个数n，输出该数每一位置的数字平方和。
- 对10取余就是获取最后一位的数值
- 除10相当于删除最后一位。
建立一个哈希set，记录此前已经出现的平方和，若平方和重复出现，则不是快乐数，若平方和为1，则退出循环，返回true。

解答

class Solution {  
public:  
    // 写一个算法将一个正整数替换为每个位置上的数字平方和  
    int getsum(int n) {  
        int sum = 0;  
        // 从个位开始逐位的计算平方和并累积到sum中  
        while (n != 0) {  
            sum += (n % 10) * (n % 10);  
            n /= 10; //使用int的整除舍弃掉最后一位数  
        }  
        return sum;  
    }  
    bool isHappy(int n) {  
        // 这道题目的难点在于要能想到无限循环意味着 平方和sum的结果重复出现了，再通过哈希算法可以判断重复继而判断快乐数  
        unordered_set<int> sumset;  
        while(true)  
        {  
            int sum = getsum(n);  
            if(sum == 1)  
                return true;  
            else if(sumset.find(sum) != sumset.end())  
                return false;  
            else  
                sumset.insert(sum);  
            n = sum;  
        }  
    }  
};

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

分析

用一个哈希表来记录已经遍历的元素和对应的下标。每次遍历一个新元素，都会用target-它自身作为key去map中找寻配对，若配对上，则return ，若没配上，则把当前元素加到map，留待后人来匹配。若整个数组都遍历完了，那返回{}。

解答

class Solution {  
public:  
    vector<int> twoSum(vector<int>& nums, int target) {  
        // 建立一个哈希表存放已经遍历过的元素  
        unordered_map <int, int> map;  
        //遍历数组  
        for (int i = 0; i < nums.size(); i++) {  
                if(map.find(target-nums[i])!=map.end()){  
                    return {map[target-nums[i]], i};  
                }  
                else{  
                    map[nums[i]]=i;  
                }  
            }  
        //返回空数组  
        return {};  
        }  
};

454. 四数相加 II

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

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

分析

用一个unordered_map 来记录nums1和nums2的和以及出现的次数，然后遍历nums3和nums4两两之间的组合，若find(-nums3[i] - nums4[j])可以找到，那结果加上对应的次数。

解答

class Solution {  
public:  
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {  
        // 遍历nums1和nums2两两之间的和，存到一个 unordered_map 中  
        unordered_map<int,int> sum12;  
        int result = 0;  
        for (int i = 0; i < nums1.size(); i++) {  
            for (int j = 0; j < nums2.size(); j++) {  
                sum12[nums1[i] + nums2[j]]++;  
            }  
        }  
        for (int i = 0; i < nums3.size(); i++) {  
            for (int j = 0; j < nums4.size(); j++) {  
                if(sum12.find(-nums3[i] - nums4[j])!= sum12.end())  
                {  
                    result += sum12[-nums3[i] - nums4[j]];  
                }  
            }  
        }  
        return result;  
    }  
};

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。 注意： 答案中不可以包含重复的三元组。注意，输出的顺序和三元组的顺序并不重要。

分析

这道题目本身用哈希也不是不可以解，但由于答案中不可以包含重复的三元组，去重太麻烦了，很难在时间限制捏a这道题目。所以卡尔建议使用双指针的方法来解决：

sort 一下整个数组，这是双指针方法的前提
遍历数组中每个元素作为a
初始化左指针，即b，为a的下一位。
初始化右指针为数组最后一位，即c。
若a+b+c 小于0，说明L++；若大于0，则R--；知道L不符合小于R时，结束当前while。即一层for循环num[i]为确定值，然后循环内有left和right下标作为双指针，找到nums[i] + nums[left] + nums[right] == 0。

[!NOTE] Title a b c三者的去重是本题最麻烦的点

解答

class Solution {  
public:  
    vector<vector<int>> threeSum(vector<int>& nums) {  
        sort(nums.begin(), nums.end());  
        vector<vector<int>> res;  
        for (int i = 0; i < nums.size()-2; i++) {  
            if (i > 0 && nums[i] == nums[i-1]) {  
                continue;  
            }  
            int left = i + 1;  
            int right = nums.size() - 1;  
            while (left < right) {  
                int sum = nums[i] + nums[left] + nums[right];  
                if (sum == 0) {  
                    res.push_back({nums[i], nums[left], nums[right]});  
                    while (left < right && nums[left] == nums[left+1]) {  
                        left++;  
                    }  
                    while (left < right && nums[right] == nums[right-1]) {  
                        right--;  
                    }  
                    left++;right--;  
                }  
                if (sum < 0) {  
                    left++;  
                } else if(sum > 0) {  
                    right--;  
                }  
            }  
        }  
        return res;  
    }  
};

18. 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target 你可以按 任意顺序 返回答案。

分析

四数之和的双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况，三数之和的时间复杂度是O(n^2)，四数之和的时间复杂度是O(n^3) 。

唯一需要的事情还是去重，a b c d 的去重是向前去排除而不是向后的。

解答

vector<vector<int>> fourSum(vector<int>& nums, int target) {  
    vector<vector<int>> res;  
    sort(nums.begin(), nums.end());  
    for (int i = 0; i < nums.size(); i++) {  
        if (i > 0 && nums[i] == nums[i-1]) {  
            continue;  
        }  
        for (int j = i + 1; j < nums.size(); j++) {  
            if (j > i+1 && nums[j] == nums[j-1]) {  
                continue;  
            }  
            int left = j + 1;  
            int right = nums.size() - 1;  
            long long sum12 = nums[i] + nums[j];  
            while (left < right) {  
                long long sum34 = nums[left] + nums[right];  
                if (sum34 < target-sum12) {  
                    left++;  
                } else if(sum34 > target-sum12) {  
                    right--;  
                }  
                else {  
                    res.push_back({nums[i],nums[j], nums[left], nums[right]});  
                    while (left < right && nums[left] == nums[left+1]) {  
                        left++;  
                    }  
                    while (left < right && nums[right] == nums[right-1]) {  
                        right--;  
                    }  
                    left++;right--;  
                }  
  
            }  
        }  
    }  
    return res;  
}

Files

哈希表篇.md

Latest commit

History

哈希表篇.md

File metadata and controls

理论基础

常见的三种哈希结构

常用的相关函数

赋值

分析

解答

分析

解答

分析

解答

分析

解答

分析

解答

分析

解答

分析

解答

分析

解答

分析

解答

分析

解答

分析

解答