哈希表

不同的数据结构有不同的作用和长处，这里哈希表是用于O(1)时间复杂度的查找。

哈希表的常用数据结构：

• 1 数组：适用于小数组，即在字母数组中进行查询或者长度不小于1000的数组。
• 2 集合：适用于key和value都一致，同时需要去重的场景。
• 3 字典：适用于数据范围宽大，同时需要key和value的场景。
  • 3.1 key,value -> key , 计数
  • 3.2 key,value -> key, 索引

1 有效的字母异位词

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

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

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

示例 2:

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

解题思路：这里只需要在字母中判断是否存在，故使用数组作为哈希表即可。

class Solution {
public:
    bool isAnagram(string s, string t) {
        int map[26] = {0};
        for(int i=0; i<s.size(); i++) map[s[i]-'a']++;
        for(int i=t.size()-1; i>=0; i--) map[t[i]-'a']--;
        for(auto m:map) if (m) return false;
        return true;
    }
};

2 两个数组的交集

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

示例 1：

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

示例 2：

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

解题思路：

• 1 该题的参数范围空间较大，故首先从set和map中选择
• 2 该题需要去重，故使用set

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> my_set;
        vector<int> result;
        for(auto n1:nums1) my_set.insert(n1);
        for(auto n2:nums2){
            if (my_set.find(n2)!=my_set.end()){
                my_set.erase(n2);
                result.push_back(n2);
            }
        }
        return result;
    }
};

3 快乐数

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

「快乐数」 定义为：

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

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

示例 1：

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

4 两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

示例 1：

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

解题思路：

• 1 大范围数组，需要key，value故使用map。
• 2 key, value -> key, 索引

Notes: 由于返回值不能重复出现，故不能先构出完整的字典，而是边构建边判断，这样才能达到去重的目的。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> my_map;
        vector<int> result;
        for(int i=0; i<nums.size(); i++){
            auto iter = my_map.find(target-nums[i]);
            if (iter!=my_map.end()){
                return {iter->second, i};
            }else{
                my_map.insert({nums[i], i});
            }
        }
        return {};
    }
};

5 四数相加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

示例 1：

输入：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

解题思路：

• 1 大范围数组，需要key，value故使用map。
• 2 key, value -> key, 计数

class Solution {
public:
    int fourSumCount(vector& nums1, vector& nums2, vector& nums3, vector& nums4) {
        int result = 0;
        unordered_map<int, int> my_map;
        for(int i=0; i<nums1.size(); i++){
            for(int j=0; j<nums2.size(); j++){
                my_map[nums1[i]+nums2[j]]++;
            }
        }
        for(int i=0; i<nums3.size(); i++){
            for(int j=0; j<nums4.size(); j++){ auto iter = my_map.find(-(nums3[i]+nums4[j])); if (iter!=my_map.end()) result += iter->second;
            }
        }
        return result;
    }
};

5 赎金信

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

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

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

示例 1：

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

解题思路：

• 1 在magazine中使用哈希表为字母进行计数（字典和数组均可）
• 2 遍历randsomNote中，数量不足或者不存在即返回false

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        unordered_map<int, int> my_map;
        for(auto m:magazine) my_map[m-'a']++;
        for(auto r:ransomNote){
            // 找到
            if (my_map[r-'a'] > 0) my_map[r-'a']--;
            // 找不到或者不够即为false否则为true
            else return false;
        }
        return true;
        
    }
};

6 三数之和/四数之和

三数之和/四数之和虽然看起来和两数之和没有什么差别都是属于哈希表的题目，但是三数之和/四数之和这俩题目涉及最终结果的去重，使用哈希法在去重的过程中需要考虑的东西太多。

故这两道题实际上更适合双指针法，先对数组进行排序后，双指针双向遍历的过程遇到重复的可以跳过，即在遍历过程中就去重了。