【哈希表】(三) 实际应用 - 哈希映射

目录

一、哈希映射 - 用法

二、场景 I - 提供更多信息

三、两数之和

3.1 题目要求

3.2 解决过程

四、同构字符串

4.1 题目要求

4.2 解决过程

四、两个列表的最小索引总和

4.1 题目要求

4.2 解决过程

六、场景 II - 按键聚合

七、字符串中的第一个唯一字符

7.1 题目要求

7.2 解决过程

八、两个数组的交集 II

8.1 题目要求

8.2 解决过程

九、存在重复元素 II

9.1 题目要求

9.2 解决过程

十、日志速率限制器 (PLUS 会员专享)

---

参考文献：https://leetcode-cn.com/leetbook/read/hash-table/xhly3j/ 

---

一、哈希映射 - 用法

// C++ implementation
#include <unordered_map>                // 0. include the library
 
int main() {
    // 1. initialize a hash map
    unordered_map<int, int> hashmap;
    // 2. insert a new (key, value) pair
    hashmap.insert(make_pair(0, 0));
    hashmap.insert(make_pair(2, 3));
    // 3. insert a new (key, value) pair or update the value of existed key
    hashmap[1] = 1;
    hashmap[1] = 2;
    // 4. get the value of a specific key
    cout << "The value of key 1 is: " << hashmap[1] << endl;
    // 5. delete a key
    hashmap.erase(2);
    // 6. check if a key is in the hash map
    if (hashmap.count(2) <= 0) {
        cout << "Key 2 is not in the hash map." << endl;
    }
    // 7. get the size of the hash map
    cout << "the size of hash map is: " << hashmap.size() << endl; 
    // 8. iterate the hash map
    for (auto it = hashmap.begin(); it != hashmap.end(); ++it) {
        cout << "(" << it->first << "," << it->second << ") ";
    }
    cout << "are in the hash map." << endl;
    // 9. clear the hash map
    hashmap.clear();
    // 10. check if the hash map is empty
    if (hashmap.empty()) {
        cout << "hash map is empty now!" << endl;
    }
}

# Python implementation
 
# 1. initialize a hash map
hashmap = {0 : 0, 2 : 3}
# 2. insert a new (key, value) pair or update the value of existed key
hashmap[1] = 1
hashmap[1] = 2
# 3. get the value of a key
print("The value of key 1 is: " + str(hashmap[1]))
# 4. delete a key
del hashmap[2]
# 5. check if a key is in the hash map
if 2 not in hashmap:
    print("Key 2 is not in the hash map.")
# 6. both key and value can have different type in a hash map
hashmap["pi"] = 3.1415
# 7. get the size of the hash map
print("The size of hash map is: " + str(len(hashmap)))
# 8. iterate the hash map
for key in hashmap:
    print("(" + str(key) + "," + str(hashmap[key]) + ")", end=" ")
print("are in the hash map.")
# 9. get all keys in hash map
print(hashmap.keys())
# 10. clear the hash map
hashmap.clear();
print("The size of hash map is: " + str(len(hashmap)))

 参考文献：https://leetcode-cn.com/leetbook/read/hash-table/xhy35e/

---

 

二、场景 I - 提供更多信息

// C++ implementation
 
/*
 * Template for using hash map to find duplicates.
 * Replace ReturnType with the actual type of your return value.
 */
ReturnType aggregateByKey_hashmap(vector<Type>& keys) {
    // Replace Type and InfoType with actual type of your key and value
    unordered_map<Type, InfoType> hashtable;
    for (Type key : keys) {
        if (hashmap.count(key) > 0) {
            if (hashmap[key] satisfies the requirement) {
                return needed_information;
            }
        }
        // Value can be any information you needed (e.g. index)
        hashmap[key] = value;
    }
    return needed_information;
}

 参考文献：https://leetcode-cn.com/leetbook/read/hash-table/xhcuhg/

---

三、两数之和

3.1 题目要求

3.2 解决过程

个人实现

法一：朴素法 - 暴力迭代法。空间复杂度 O(1)，时间复杂度 O(n²)。

2020/08/21 - 26.06% (3552ms)

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)-1):  # 当前数值
            cur = target - nums[i]  # 待寻找数值
            for j in range(i+1, len(nums)):  # 被比较数值
                if cur == nums[j]:
                    return [i, j]

法二：散列表 / 哈希表。牺牲空间换取时间。结合题目和提示可使用字典形式的哈希表实现 (当然，由全0初始化列表构造的 HashTable 亦可)。

具体而言，先用 target 减去列表中的首个元素值，并将该元素值作为 key、元素值的下标/索引作为 value 存入字典。接着 target 依次减去列表中的其余元素值，并判断差是否作为 key 存在于字典中。若存在，则表示列表中存在两值之和等于 target，此时可直接返回答案，即 key 对应的 value 及当前元素值的 index。若不存在，则同理将该元素值及其索引作为 <key, value> 存入字典。通过字典存储可以实现去重。空间复杂度 O(n)，时间复杂度 O(n)。

2020/08/21 - 97.22% (56ms) - 最佳

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}  # 字典形式的 hashmap (使用全0初始化的列表也可以)
        for index, num in enumerate(nums):
            cur = target-num
            if cur in hashmap:
                return [hashmap[cur], index]  # 找到两数之和满足, 返回二者 index
            else:
                hashmap[num] = index  # 否则, 将当前元素及其索引作为 key-value 加入 hashmap

判断值是否在某个容器 (container) 中，能做到 O(1) 时间复杂度查找 的便是最常用的 散列表 (HashTable)， Python 内置数据类型中的字典即是。就本题而言，key 为标记元素值，value 为元素值下标/索引，所以更加确定使用字典这个数据结构。

此外，若使用 Python 内置 index() 函数，则因其复杂度为 O(n) 将使整个程序的复杂度达到 O(n²) (结合外层 for 循环的 O(n))；若选择使用两个 for 循环，则虽然能取得 O(1) 的空间复杂度，但却将达到 O(n²) 的时间复杂度；此二者均为低效的解法，而使用散列表则能够实现 牺牲空间换取时间，且实际中能找到节省时间的解往往更有价值。

参考文献

https://leetcode-cn.com/problems/two-sum/submissions/

---

 

四、同构字符串

4.1 题目要求

4.2 解决过程

个人实现

法一：哈希映射。分别记录 s 和 t 的各字符及其位置索引到哈希映射 (dict) 中，然后一一比较各 key 的 value 是否一致。关于 zip() 函数 的使用详见 链接。空间复杂度 O(n)，时间复杂度 O(n)。

2020/08/25 - 81.63% (48ms)

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        hashmap_s = {}  # s 的哈希映射表
        hashmap_t = {}  # t 的哈希映射表
        
        # 添加各字符及其位置索引到哈希映射表中
        for i in range(len(s)):
            # 把 s 的单字符 s[i] 作为 key, 位置索引 i 作为 value
            if not hashmap_s.get(s[i]):
                hashmap_s[s[i]] = [i]
            else:
                hashmap_s[s[i]].append(i)
            # 把 t 的单字符 t[i] 作为 key, 位置索引 i 作为 value    
            if not hashmap_t.get(t[i]):
                hashmap_t[t[i]] = [i]
            else:
                hashmap_t[t[i]].append(i)
                
        # 根据哈希映射表, 逐对比较位置索引列表是否一致 (不能直接比较 dict.values() 因为无序)
        for keys in zip(hashmap_s.keys(), hashmap_t.keys()):
            if hashmap_s[keys[0]] != hashmap_t[keys[1]]:
                return False
        return True

法一改：哈希映射。不仅使用 默认字典 类型来简化书写，还改为在添加位置索引后就进行比较。因为对于同构字符串，其每次添加单个字符作为 key 后，key 对应的索引列表 value 必定一致，否则不为同构字符串。关于 collections.default 详见 链接。空间复杂度 O(n)，时间复杂度 O(n)。

2020/08/25 - 97.50% (40ms) - 最佳

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        # 使用默认字典 defaultdict 简化书写
        hashmap_s = collections.defaultdict(list)  # s 的哈希映射表(默认类型为list的默认字典)
        hashmap_t = collections.defaultdict(list)  # t 的哈希映射表(默认类型为list的默认字典)
        
        # 添加各字符及其位置索引到哈希映射表中
        for i in range(len(s)):
            # 每添加一次索引
            hashmap_s[s[i]].append(i)
            hashmap_t[t[i]].append(i)
            # 就比较一次索引
            if hashmap_s[s[i]] != hashmap_t[t[i]]:
                return False
        return True

法二：内置函数组合。关于单星号操作符 * 详见 链接；关于高阶函数 map() 详见 链接。

2020/08/25 - 91.95% (44ms)

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        #return [*map(s.index, s)] == [*map(t.index, t)]
        return list(map(s.index, s)) == list(map(t.index, t))

当然，实质上并不推荐使用 Python 高阶函数解题，一是不好分析复杂度，二是缺乏通用性。

参考文献

https://leetcode-cn.com/leetbook/read/hash-table/xhjvbj/

---

四、两个列表的最小索引总和

4.1 题目要求

4.2 解决过程

个人实现

法一：哈希映射。先将 list1 中各元素 - 饭店名作为 key，索引作为 value 保存在哈希映射中。然后新建遍历 min_index 用于维护最小索引组合，min_place 则为最小索引组合对应饭店名列表。接着，遍历 list2 一一查找、比较和更新结果。最终，返回 min_place。

空间复杂度 O(len(list1) × len(str_avg))，其中 len(list1) 是 list1 长度，len(str_avg) 是 list1 中字符串平均长度。

时间复杂度 O(len(list1) × len(list2))，其中 len(list1) 是 list1 长度，len(list2) 是 list2 长度。

2020/08/25 - 98.25% (172ms) - 最佳

class Solution:
    def findRestaurant(self, list1: List[str], list2: List[str]) -> List[str]:
        # 将 list1 中各元素 - 饭店名作为 key, 索引作为 value 保存在哈希映射中
        hashmap = {}
        for i in range(len(list1)):
            hashmap[list1[i]] = i
        
        min_index = float("Inf")  # 当前最小索引组合
        min_place = []  # 当前最小索引餐厅
        
        for j in range(len(list2)):
            index = hashmap.get(list2[j])  # 提取索引 index
            if index is not None:  # 若存在索引 index, 则表明有共同喜爱的餐厅
                new_index = index + j  # 当前新索引
                if min_index == new_index:
                    min_place.append(list2[j])  # 补增餐厅名
                elif min_index > new_index:
                    min_index = new_index  # 更新最小索引组合
                    min_place = [list2[j]]  # 更新最小索引餐厅
                    
        return min_place

 参考文献

https://leetcode-cn.com/leetbook/read/hash-table/xhfact/

https://leetcode-cn.com/problems/minimum-index-sum-of-two-lists/solution/liang-ge-lie-biao-de-zui-xiao-suo-yin-zong-he-by-l/

---

六、场景 II - 按键聚合

// C++ implementation
 
/*
 * Template for using hash map to find duplicates.
 * Replace ReturnType with the actual type of your return value.
 */
ReturnType aggregateByKey_hashmap(vector<Type>& keys) {
    // Replace Type and InfoType with actual type of your key and value
    unordered_map<Type, InfoType> hashtable;
    for (Type key : keys) {
        if (hashmap.count(key) > 0) {
            update hashmap[key];
        }
        // Value can be any information you needed (e.g. index)
        hashmap[key] = value;
    }
    return needed_information;
}

参考文献：https://leetcode-cn.com/leetbook/read/hash-table/xxhryr/

---

七、字符串中的第一个唯一字符

7.1 题目要求

7.2 解决过程

个人实现

法一：哈希映射。先遍历字符串，将各字符及其位置索引加入哈希映射。然后遍历哈希映射表的键，输出首个单次出现的字符索引，否则输出 -1。空间复杂度 O(n)，时间复杂度 O(n)。

2020/08/25 - 37.03% (164ms)

class Solution:
    def firstUniqChar(self, s: str) -> int:
        # key=char : value=index
        hashmap = {}
        # 遍历字符串, 将各字符及其索引加入哈希映射中
        for i in range(len(s)):
            if hashmap.get(s[i]) is None:
                hashmap[s[i]] = [i]
            else:
                hashmap[s[i]].append(i)
        # 遍历哈希映射表的键, 输出首个单次出现的字符索引
        for j in hashmap.keys():
            if len(hashmap[j]) == 1:
                return hashmap[j][0]
        return -1

法一改：哈希映射。使用默认字典简化书写。关于 collections.default 详见 链接。空间复杂度 O(n)，时间复杂度 O(n)。

2020/08/25 - 65.93% (124ms) - 快了不少

class Solution:
    def firstUniqChar(self, s: str) -> int:
        # key=char : value=index
        hashmap = collections.defaultdict(list)
        
        for i in range(len(s)):
            hashmap[s[i]].append(i)
                
        for j in hashmap.keys():
            if len(hashmap[j]) == 1:
                return hashmap[j][0]
        return -1

 法二：哈希映射计数器。关于 collections.Counter 详见 链接。空间复杂度 O(n)，时间复杂度 O(n)。

2020/08/25 - 83.80% (104ms) - 快了更多

class Solution:
    def firstUniqChar(self, s: str) -> int:
        counter = collections.Counter(s)
        for i in range(len(s)):
            if counter[s[i]] == 1:  # 如果遇到首个仅出现单次的字符
                return i  # 即为目标字符, 返回其索引
        return -1

---

其他实现与说明

class Solution(object):
    def firstUniqChar(self, s: str) -> int:
        # 先假设最小索引为最后的字符索引
        min_unique_char_index = len(s)
 
        # 已知字符串由小写字母构成，则遍历a-z
        for c in "abcdefghijklmnopqrstuvwxyz":
            i = s.find(c)
            # 分别从目标的字符串头和字符串尾查找对应字母的索引；如果两索引相等，则说明是单一字符
            if i != -1 and i == s.rfind(c):
                # 更新最新的最小索引
                min_unique_char_index = min(min_unique_char_index, i)
 
        # 如果返回值不为最后字符的索引，则返回最小索引值
        # 否则，根据题意，返回-1
        return min_unique_char_index if min_unique_char_index != len(s) else -1

2020/08/25 - 99.94% (36ms) - 最佳 - 虽然很快，但内置函数的使用还是要慎重

以下实现表面上看起来更简单，但实际性能差很多，只有约 60%：

class Solution(object):
    def firstUniqChar(self, s: str) -> int:
        for c in s:
            index = s.find(c)
            if index == s.rfind(c):
                return index
        return -1

---

class Solution(object):
    def firstUniqChar(self, s: str) -> int:
        odict = collections.OrderedDict()
 
        # 记录字符出现次数
        for c in s:
            odict[c] = odict[c] + 1 if c in odict else 1
 
        # 利用有序的特性，在字典中找出首个出现次数为一的字符串
        for k, v in odict.items():
            if v == 1:
                # 返回字符串首次出现的位置
                return s.index(k)
 
        return -1

 2020/08/25 - 65.93% (124ms)

以上实现虽然还行，但尽量不使用其他内置函数为妙。 

参考文献

https://leetcode-cn.com/leetbook/read/hash-table/xxx94s/

https://leetcode-cn.com/problems/first-unique-character-in-a-string/solution/zi-fu-chuan-zhong-de-di-yi-ge-wei-yi-zi-fu-by-leet/

https://leetcode-cn.com/problems/first-unique-character-in-a-string/solution/python-4chong-fang-fa-yi-ge-12msde-gai-jin-jie-fa-/

---

 

八、两个数组的交集 II

8.1 题目要求

8.2 解决过程

个人实现

法一：哈希映射。空间复杂度 O(n)，时间复杂度 O(n)。

2020/08/25 - 92.19% (56ms)

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # nums1 元素计数器 - dict 实现
        hashmap = {}
        for i in range(len(nums1)):
            if hashmap.get(nums1[i]) is None:
                hashmap[nums1[i]] = 0  # 零值初始化
            hashmap[nums1[i]] += 1  # 计数+1
        
        result = []
        for j in range(len(nums2)):
            if hashmap.get(nums2[j]):  # 计数非空非零
                result.append(nums2[j])  # 结果添加
                hashmap[nums2[j]] -= 1  # 计数-1
        
        return result

法一改：哈希映射。使用默认字典简化书写。关于 collections.default 详见 链接。空间复杂度 O(n)，时间复杂度 O(n)。

2020/08/25 - 92.19% (56ms)

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # nums1 元素计数器 - defaultdict 实现
        hashmap = collections.defaultdict(int)
        for i in range(len(nums1)):
            hashmap[nums1[i]] += 1  # 计数+1
        
        result = []
        for j in range(len(nums2)):
            if hashmap.get(nums2[j]):  # 计数非空非零
                result.append(nums2[j])  # 结果添加
                hashmap[nums2[j]] -= 1  # 计数-1
        
        return result

法一改：哈希映射计数器。关于 collections.Counter 详见 链接。空间复杂度 O(n)，时间复杂度 O(n)。

2020/08/25 - 80.74% (60ms)

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # nums1 元素计数器 - Counter 实现
        hashmap = collections.Counter(nums1)
        result = []  # 结果列表
        for j in range(len(nums2)):
            n = nums2[j]  # 当前数字
            if hashmap.get(n):  # 计数非空非零
                result.append(n)  # 结果添加
                hashmap[n] -= 1  # 计数-1
        
        return result

甚至可以更多地使用 Counter 特性完成：

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        num1 = collections.Counter(nums1)
        num2 = collections.Counter(nums2)
        num = num1 & num2
        return num.elements()

 法三：数组排序 + 双指针。空间复杂度 O(n)，时间复杂度 O(nlong)。

2020/08/25 - 63.67% (64ms)

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()  # nums1 排序
        nums2.sort()  # nums2 排序
        result = []  # 结果列表
        ptr1 = 0  # nums1 指针
        ptr2 = 0  # nums2 指针
        
        while ptr1 < len(nums1) and ptr2 < len(nums2):
            n1 = nums1[ptr1]  # 当前 nums1 元素
            n2 = nums2[ptr2]  # 当前 nums2 元素
            if n1 == n2:
                result.append(n1)
                ptr1 += 1
                ptr2 += 1
            elif n1 > n2:
                ptr2 += 1
            else:
                ptr1 += 1
        
        return result

---

官方实现与说明

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if len(nums1) > len(nums2):
            return self.intersect(nums2, nums1)  # 强行令短左长右
        
        m = collections.Counter()
        for num in nums1:
            m[num] += 1
        
        intersection = list()
        for num in nums2:
            if (count := m.get(num, 0)) > 0:  # := 是海象运算符
                intersection.append(num)
                m[num] -= 1
                if m[num] == 0:
                    m.pop(num)
 
        return intersection

2020/08/25 - 80.74% (60ms) 

---

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
 
        length1, length2 = len(nums1), len(nums2)
        intersection = list()
        index1 = index2 = 0
        while index1 < length1 and index2 < length2:
            if nums1[index1] < nums2[index2]:
                index1 += 1
            elif nums1[index1] > nums2[index2]:
                index2 += 1
            else:
                intersection.append(nums1[index1])
                index1 += 1
                index2 += 1
        
        return intersection

参考文献

https://leetcode-cn.com/leetbook/read/hash-table/xx5hsd/

https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/solution/liang-ge-shu-zu-de-jiao-ji-ii-by-leetcode-solution/

https://leetcode-cn.com/problems/intersection-of-two-arrays-ii/solution/jin-jie-san-wen-by-user5707f/

---

九、存在重复元素 II

9.1 题目要求

9.2 解决过程

个人实现

法一：哈希映射。用哈希表记录当前数字最后一次遇到时的索引，然后根据条件要求判断或更新。空间复杂度 O(n)，时间复杂度 O(n)。

2020/08/25 - 89.02% (44ms) - 最佳

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # key=num : value=index
        hashmap = {}
        for i in range(len(nums)):
            index = hashmap.get(nums[i])
            if (index is None) or (i-index > k):  # (abs(index-i) > k) 由于后来的肯定比之前的 index 大, 故 abs() 可不用
                hashmap[nums[i]] = i  # 当前数字索引为空(尚未记录)或不符合要求, 则更新之
            else:
                return True
            
        return False

---

官方实现与说明

// Java implementation
public boolean containsNearbyDuplicate(int[] nums, int k) {
    for (int i = 0; i < nums.length; ++i) {
        for (int j = Math.max(i - k, 0); j < i; ++j) {
            if (nums[i] == nums[j]) return true;
        }
    }
    return false;
}
// Time Limit Exceeded.

---

// Java implementation
public boolean containsNearbyDuplicate(int[] nums, int k) {
    Set<Integer> set = new TreeSet<>();
    for (int i = 0; i < nums.length; ++i) {
        if (set.contains(nums[i])) return true;
        set.add(nums[i]);
        if (set.size() > k) {
            set.remove(nums[i - k]);
        }
    }
    return false;
}
// Time Limit Exceeded.

---

// Java implementation
public boolean containsNearbyDuplicate(int[] nums, int k) {
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < nums.length; ++i) {
        if (set.contains(nums[i])) return true;
        set.add(nums[i]);
        if (set.size() > k) {
            set.remove(nums[i - k]);
        }
    }
    return false;
}

# Python implementation
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # 维护一个 k 长度的哈希集合
        hashset = set()
        for i in range(len(nums)):
            # 若当前数字存在于哈希集合中, 则满足条件
            if nums[i] in hashset:
                return True
            # 否则, 将当前数字存入哈希集合
            hashset.add(nums[i])
            # 哈希集合超长时, 剔除最早进入的数字
            if len(hashset) > k:
                hashset.remove(nums[i-k])
            
        return False

 2020/08/25 - 76.34% (48ms)

参考文献

https://leetcode-cn.com/leetbook/read/hash-table/xx5bzh/

https://leetcode-cn.com/problems/contains-duplicate-ii/solution/cun-zai-zhong-fu-yuan-su-ii-by-leetcode/

---

十、日志速率限制器 (PLUS 会员专享)