Lesson 11: unordered_map 专题

目录

1. 知识介绍

• 1.1 哈希表常用操作

• 1.2 哈希表简单实现

• 1.3 哈希冲突与扩容

• 1.4 unordered_map 和 map 的区别

2. 频率统计与计数

• 2.1 词频统计介绍

• 2.2 例题讲解

  • 2.2.1 LC 242 有效的字母异位词

• 2.3 举一反三

  • 2.3.1 LC 387 字符串中的第一个唯一字符

3. 快速查找

• 3.1 快速查找介绍

• 3.2 例题讲解

  • 3.2.1 LC 1 两数之和

• 3.3 举一反三

  • 3.3.1 LC 217 存在重复元素

4. 哈希映射

• 4.1 哈希映射介绍

• 4.2 例题讲解

  • 4.2.1 LC 697 数组的度

• 4.3 举一反三

  • 4.3.1 LC 205 同构字符串

  • 4.3.2 LC 219 存在重复元素II

5. 课后练习

1 知识介绍

在 C++ 中，unordered_map 和 map 都是用于存储键值对的容器。unordered_map 是一种高效的哈希表实现，提供了非常快速的查找、插入和删除操作（本章重点讲解 unordered_map）。 map是基于红黑树实现的有序键值对容器。哈希表（hash table）通过建立键 key 与值 value 之间的映射，实现高效的元素查询。具体而言，我们向哈希表中输入一个键 key，则可以快速获取对应的值 value。

给定 n 个学生，每个学生都有“姓名”和“学号”两项数据。假如我们希望实现“输入一个学号，返回对应的姓名”的查询功能，则可以采用下图所示的哈希表来实现。

1.1 哈希表常用操作

哈希表的常见操作包括：初始化、查询操作、添加键值对和删除键值对等。

#include <unordered_map>
#include <iostream>
using namespace std;

int main() {
    // 初始化哈希表
    unordered_map<int, string> hmap;

    // 添加操作：在哈希表中添加键值对 (key, value)
    hmap[12836] = "小哈";
    hmap[15937] = "小啰";
    hmap[16750] = "小算";
    hmap[13276] = "小法";
    hmap[10583] = "小鸭";

    // 查询操作：向哈希表中输入键 key，得到值 value
    string name = hmap[15937];
    cout << name << endl; // 输出: 小啰

    // 删除操作：在哈希表中删除键值对 (key, value)
    hmap.erase(10583);
    for (const auto& pair : hmap) {
        cout << pair.first << " -> " << pair.second << endl;
    }

    // 修改操作
    hmap[10583] = "小鹅";
    for (const auto& pair : hmap) {
        cout << pair.first << " -> " << pair.second << endl;
    }

    return 0;
}

输出：

小啰
12836 -> 小哈
15937 -> 小啰
16750 -> 小算
13276 -> 小法
12836 -> 小哈
15937 -> 小啰
16750 -> 小算
13276 -> 小法
10583 -> 小鹅

哈希表的遍历有三种常用方式：遍历键值对、遍历键和遍历值。示例代码如下：

#include <unordered_map>
#include <iostream>
using namespace std;

int main() {
    unordered_map<int, string> hmap;
    hmap[12836] = "小哈";
    hmap[15937] = "小啰";
    hmap[16750] = "小算";
    hmap[13276] = "小法";
    hmap[10583] = "小鸭";

    // 遍历哈希表：遍历键值对 key->value
    for (const auto& pair : hmap) {
        cout << pair.first << " -> " << pair.second << endl;
    }

    // 遍历键 key
    for (const auto& pair : hmap) {
        cout << pair.first << endl;
    }

    // 遍历值 value
    for (const auto& pair : hmap) {
        cout << pair.second << endl;
    }

    return 0;
}

输出：

12836 -> 小哈
15937 -> 小啰
16750 -> 小算
13276 -> 小法
10583 -> 小鸭
12836
15937
16750
13276
10583
小哈
小啰
小算
小法
小鸭

1.2 哈希表简单实现

我们先考虑最简单的情况，仅用一个数组来实现哈希表。在哈希表中，我们将数组中的每个空位称为桶（bucket），每个桶可存储一个键值对。因此，查询操作就是找到 key 对应的桶，并在桶中获取 value 。

那么，如何基于 key 定位对应的桶呢？这是通过哈希函数（hash function）实现的。哈希函数的作用是将一个较大的输入空间映射到一个较小的输出空间。在哈希表中，输入空间是所有 key ，输出空间是所有桶（数组索引）。换句话说，输入一个 key ，我们可以通过哈希函数得到该 key 对应的键值对在数组中的存储位置。

输入一个 key ，哈希函数的计算过程分为以下两步。

1. 通过某种哈希算法 hash() 计算得到哈希值。

2. 将哈希值对桶数量（数组长度）capacity 取模，从而获取该 key 对应的数组索引 index。

index = hash(key) % capacity

随后，我们就可以利用 index 在哈希表中访问对应的桶，从而获取 value 。

设数组长度 capacity = 100、哈希算法 hash(key) = key ，易得哈希函数为 key % 100 。下图以 key 学号和 value 姓名为例，展示了哈希函数的工作原理。 下图展示了哈希函数的工作原理：

1.3 哈希冲突与扩容

从本质上看，哈希函数的作用是将所有 key 构成的输入空间映射到数组所有索引构成的输出空间，而输入空间往往远大于输出空间。因此，理论上一定存在“多个输入对应相同输出”的情况。

对于上述示例中的哈希函数，当输入的 key 后两位相同时，哈希函数的输出结果也相同。例如，查询学号为 12836 和 20336 的两个学生时，我们得到：

12836 % 100 = 36
20336 % 100 = 36

如下图所示，两个学号指向了同一个姓名，这显然是不对的。我们将这种多个输入对应同一输出的情况称为哈希冲突（hash collision）。

如果出现哈希冲突了，只是会降低查找的性能，因为同一个哈希值对应的桶当中，还会以链表的形式存储多个值，如果发现哈希冲突，就会沿着链表查找，因为是遍历，所以性能会降低。

容易想到，哈希表容量 n 越大，多个 key 被分配到同一个桶中的概率就越低，冲突就越少。因此，我们可以通过扩容哈希表来减少哈希冲突。

如下图所示，扩容前键值对 (136, A) 和 (236, D) 发生冲突，扩容后冲突消失。

类似于数组扩容，哈希表扩容需将所有键值对从原哈希表迁移至新哈希表，非常耗时；并且由于哈希表容量 capacity 改变，我们需要通过哈希函数来重新计算所有键值对的存储位置，这进一步增加了扩容过程的计算开销。为此，编程语言通常会预留足够大的哈希表容量，防止频繁扩容。

1.4 unordered_map 和 map 的区别

在前面的讲解中，我们简单提到了 map，它是基于红黑树实现的，并且能够按顺序存储键值对。而在 C++ 中，unordered_map 和 map 都是用于存储键值对的容器，但它们的实现方式和使用场景有所不同。这里简单提一下它们的区别，大家了解一下就好，不需要深入理解。

特性	unordered_map	map
底层实现	哈希表	红黑树
键值对顺序	无序存储	按键的升序存储
查找效率	查找速度更快，适合快速查找的场景	查找较慢，但键值对自动有序存储
使用场景	适合频繁查找、插入、删除的操作	适合需要按顺序存储和访问的场景

为什么 unordered_map 比 map 快？

• unordered_map 使用哈希表实现：unordered_map 通过哈希函数来处理每个键。你可以把哈希函数想象成一个智能快递员，负责把每个键（类似于包裹）送到一个特定的地址（也就是存储位置）。这个“地址”不是随意的，而是通过一个固定的计算方式（哈希函数）来确定的。

  举个例子：

  • 你有一个键值对，键是 "apple"，值是 "fruit"。
  • 哈希函数会拿到 "apple" 这个键，进行某种计算（就像快递员根据地址去分类包裹一样），然后直接把它送到指定的位置，比如内存的某个“桶”（bucket）里。
  • 当你之后想查找 "apple" 对应的值时，哈希函数会再次根据 "apple" 进行同样的计算，告诉你它被放在内存的哪个“桶”里。由于这个计算非常直接，速度非常快。

  为什么这样快？

  • 因为哈希函数是直接计算出结果，而不是像 map 那样按顺序逐个比对键。unordered_map 不需要排序或者对比，只要通过哈希函数找到正确的“桶”，就能快速定位数据，类似于快递员把包裹放到准确的位置。

  无序存储的原因：

  • 因为哈希表中的键值对是根据哈希函数的结果来放置的，顺序取决于哈希函数的计算结果。因此，插入和查找时不需要关心顺序，只要计算出“桶”的位置，就能立刻访问数据。

• map 使用红黑树实现：map 会自动保持键值对的顺序，因此每次插入、删除和查找时都需要进行键的比对和排序操作。由于这些操作的存在，map 的速度比 unordered_map 稍慢，但它能保证数据有序。

总结：

• 如果你不需要数据有序，且需要快速查找、插入或删除，unordered_map 更适合。
• 如果你需要按顺序存储键值对，那么 map 更合适，即便查找速度稍慢一些。

2 频率统计与计数

2.1 词频统计介绍

哈希表（unordered_map）最常见的用途之一是频率统计，即用来统计数据出现的次数或频率。在需要处理大量数据时，哈希表可以通过键值对快速记录每个元素的出现次数。这样的操作时间复杂度为 O(1)，因此相比于使用数组或列表的 O(n) 查找，性能大幅提升。

词频统计是哈希映射的一种特殊应用，重点在于将一个值（如字符、数字等）映射到其出现次数上。它狭义地定义了键值对中的“值”是该键出现的频率，常用于统计数据集中的元素频率。词频统计通常用于字符统计、元素频率统计等。

简单来说，词频统计是一种特定的哈希映射，狭义地将键值对定义为“元素: 出现频率”，用于频率统计问题中。

例如，在字符串中统计每个字符的出现频率时，哈希表的键是字符，值是该字符的出现次数。

常见应用：

• 查找出现次数最多的元素
• 判断数据集中是否存在重复元素
• 统计每个字符/数字/元素的频率

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

unordered_map<char, int> count_frequency(const string& s) {
    std::unordered_map<char, int> freq_dict;
    for (char c : s) {
        if (freq_dict.find(c) != freq_dict.end()) {
            freq_dict[c] += 1;
        } else {
            freq_dict[c] = 1;
        }
    }
    return freq_dict;
}

2.2 例题讲解

2.2.1 LC 242 有效的字母异位词

问题描述

描述：给定两个字符串s和t。

要求：判断t和s是否使用了相同的字符构成（字符出现的种类和数目都相同

思路分析

1. 如果两个字符串的长度不同，直接返回 false，因为它们不可能是字母异位词。

2. 如果长度相同，使用 unordered_map 来统计第一个字符串 s 中每个字符的出现次数，然后遍历字符串 t，相应地减少字符的出现次数。如果在某个时刻字符的频率小于 0，表示 t 中字符的出现次数多于 s，此时直接返回 false。

提示

创建两个 unordered_map 储存频率次数，进行比较。

参考解答：

class Solution {
public:
    bool isAnagram(string s, string t) {
        // 如果两个字符串长度不同，直接返回 false
        if (s.length() != t.length()) {
            return false;
        }

        // 使用两个 unordered_map 来统计两个字符串中每个字符的频率
        unordered_map<char, int> count_s, count_t;

        // 遍历两个字符串，统计每个字符的频率
        for (int i = 0; i < s.length(); ++i) {
            count_s[s[i]]++;
            count_t[t[i]]++;
        }

        // 比较两个频率表是否相等
        return count_s == count_t;
    }
};

2.3 举一反三

2.3.1 LC 387 字符串中的第一个唯一数字

问题描述

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1。

思路分析

为了找到字符串中第一个不重复的字符，我们可以使用两次遍历的方式：

1. 第一次遍历：使用哈希表（unordered_map）记录每个字符出现的次数。
2. 第二次遍历：检查每个字符的出现次数，并找到第一个出现次数为 1 的字符，返回它的索引。
3. 如果没有找到任何符合条件的字符，返回 -1。

提示

• 哈希表（unordered_map）能够有效地记录每个字符的频率。
• 我们通过两次遍历来完成这个任务，第一次遍历统计频率，第二次遍历查找第一个不重复的字符。

参考示例

class Solution {
public:
    int firstUniqChar(string s) {
        // 使用 unordered_map 统计每个字符的出现次数
        unordered_map<char, int> count;

        // 第一次遍历字符串，记录每个字符的出现次数
        for (int i = 0; i < s.length(); ++i) {
            count[s[i]]++;
        }

        // 第二次遍历字符串，找到第一个出现次数为 1 的字符
        for (int i = 0; i < s.length(); ++i) {
            if (count[s[i]] == 1) {
                return i;  // 返回第一个不重复字符的索引
            }
        }

        // 如果没有找到不重复的字符，返回 -1
        return -1;
    }
};

3 快速查找

3.1 快速查找介绍

快速查找是通过哈希表（unordered_map）实现的，它利用哈希函数的性质在常数时间内完成查找任务。其核心在于高效性——相比于列表遍历的 O(n) 时间复杂度，哈希表通过哈希查找可以在 O(1) 时间内找到对应的值。快速查找并不关心具体的映射关系，而是着重强调查找速度的提升。

简单来说，快速查找是哈希表利用哈希函数实现的高效查找操作，强调时间复杂度为 O(1)，适用于在数据集中快速定位特定元素。

例如，通过给定学生学号，查找对应的学生姓名时，哈希表可以快速返回查询结果。

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    // 创建哈希表，存储学号和姓名
    unordered_map<int, string> students = {
        {1001, "Alice"},
        {1002, "Bob"},
        {1003, "Charlie"}
    };

    // 根据学号快速查找对应的学生姓名
    int student_id = 1002;
    cout << students[student_id] << endl;  // 输出：Bob

    return 0;
}

3.2例题讲解

3.2.1 LC 1 两数之和

问题描述

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

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

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

思路分析

遍历数组，对于每一个数 nums[i]：

1. 查找哈希表中是否存在 target - nums[i]，如果存在，则输出 target - nums[i] 对应的下标和当前数组的下标 i。
2. 如果不存在，则将 nums[i] 和下标 i 存入哈希表中。

提示

属于 unordered_map 中的快速查找。

参考解答：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;  // 用于存储数值和其对应的下标
        for (int i = 0; i < nums.size(); i++) {
            int complement = target - nums[i];  // 计算差值
            if (hashtable.find(complement) != hashtable.end()) {  // 如果差值在哈希表中
                return {hashtable[complement], i};  // 返回差值对应的下标和当前下标
            }
            hashtable[nums[i]] = i;  // 将当前值和下标存入哈希表
        }
        return {};  // 如果没有找到，返回空数组
    }
};

3.3 举一反三

3.3.1 LC 217 存在重复元素

问题描述

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true；如果数组中每个元素互不相同，返回 false。

思路分析

这道题目要求判断一个数组中是否存在重复的数字。可以使用一个 unordered_map 来存储每个数字是否已经出现过。遍历数组时，每遇到一个数字，就检查它是否已经存在于 unordered_map 中。如果已经存在，说明该数字重复了，直接返回 true；如果没有，就将该数字加入 unordered_map 中，继续检查下一个数字。遍历完数组后，如果没有找到任何重复的数字，就返回 false。

这样做的好处是每个数字只会检查一次，并且查找和存储数字的操作也很快，因此整个过程很高效。

提示

unordered_map可以用来快速存储和查找数字，这样可以避免重复的数字，属于频率统计与计数。

参考解答：

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_map<int, bool> seen;  // 创建一个 unordered_map 用于存储数字
        for (int num : nums) {
            if (seen.find(num) != seen.end()) {
                return true;  // 如果数字已经存在于 map 中，说明重复
            }
            seen[num] = true;  // 否则将该数字存储到 map 中
        }
        return false;  // 遍历结束后没有找到重复的数字
    }
};

4 哈希映射

4.1 哈希映射介绍

哈希映射是一个更广泛的概念，表示通过哈希函数将一个键（key）映射到一个值（value），这种键值对可以用于构建各种关系，不仅限于频率统计或快速查找。例如，将人名映射到学校，或者将学校映射到一个包含所有学生的人名列表，都是哈希映射的应用。哈希映射可以支持一对一、一对多等复杂的关系结构。

简单来说，哈希映射是广泛使用的映射机制，能够灵活实现键值对关系，应用于更多复杂场景，如一对一、一对多的映射。

例如，将人名与学校关联，或将学校与其所有学生关联，都可以通过哈希映射来实现。

#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
using namespace std;

int main() {
    // 人名到学校的一对一映射
    unordered_map<string, string> people_to_school = {
        {"Alice", "Harvard"},
        {"Bob", "MIT"}
    };

    // 学校到人名列表的一对多映射
    unordered_map<string, vector<string>> school_to_people = {
        {"Harvard", {"Alice", "Charlie"}},
        {"MIT", {"Bob"}}
    };
}

4.2 例题讲解

4.2.1 LC 697 数组的度

问题描述

给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。

你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

思路分析

记原数组中出现次数最多的数为 x，那么和原数组的度相同的最短连续子数组，必然包含了原数组中的全部 x，且两端恰为 x 第一次出现和最后一次出现的位置。

因为符合条件的 x 可能有多个，即多个不同的数在原数组中出现次数相同。所以为了找到这个子数组，我们需要统计每一个数出现的次数，同时还需要统计每一个数第一次出现和最后一次出现的位置。

在实际代码中，我们使用哈希表实现该功能，每一个数映射到一个长度为 3 的数组，数组中的三个元素分别代表这个数出现的次数、这个数在原数组中第一次出现的位置和这个数在原数组中最后一次出现的位置。当我们记录完所有信息后，我们需要遍历该哈希表，找到元素出现次数最多，且前后位置差最小的数。

提示

1. 先记录每个元素出现的次数，第一次和最后一次的索引。

2. 找到数组的度和最短子数组的长度。

参考解答

class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        unordered_map<int, vector<int>> mp; // 存储每个数字的出现次数、第一次出现位置、最后一次出现位置

        for (int i = 0; i < nums.size(); ++i) {
            if (mp.count(nums[i])) {
                mp[nums[i]][0] += 1;   // 统计出现次数
                mp[nums[i]][2] = i;    // 更新最后一次出现的位置
            } else {
                mp[nums[i]] = {1, i, i}; // 初始化：出现次数为1，第一次和最后一次出现位置相同
            }
        }

        int maxNum = 0, minLen = nums.size();
        for (const auto& [num, data] : mp) {
            int count = data[0], left = data[1], right = data[2];
            if (count > maxNum) {
                maxNum = count; 
                minLen = right - left + 1; // 更新最短长度
            } else if (count == maxNum) {
                minLen = min(minLen, right - left + 1); // 如果出现次数相同，更新最短长度
            }
        }

        return minLen;
    }
};

解题过程：

1. 初始化字典 mp：存储每个数字的出现次数，第一次出现的索引，最后一次出现的索引。

2. 遍历数组 nums：记录出现次数，第一次出现的索引，最后一次出现的索引。

3. 遍历字典 mp 的值：提取每个数字的出现次数、第一次和最后一次出现的位置。

4. maxNum 记录当前出现次数最多的值（即数组的度）。

5. minLen 记录具有相同度的子数组的最短长度。

6. 如果当前元素的出现次数大于 maxNum，更新 maxNum 和最短子数组长度 minLen。

7. 如果出现次数相同，检查当前子数组是否比之前的短，并更新 minLen。

4.3 举一反三

4.3.1 LC 205 同构字符串

问题描述

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

思路分析

根据题意，字符串 s 和 t 中的字符在每个位置上的对应关系是一一对应的。因此，考虑用两个哈希表（unordered_map）来存储映射关系： 1. s 的每个字符与 t 的字符建立映射。 2. t 的每个字符与 s 的字符建立映射，确保映射的唯一性。

提示

属于建立映射，通过创建 unordered_map 建立字母和出现字母的映射关系。

参考解答

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, char> s_to_t; // s -> t 的映射
        unordered_map<char, char> t_to_s; // t -> s 的映射

        for (int i = 0; i < s.size(); i++) {
            char s_char = s[i];
            char t_char = t[i];

            // 检查 s -> t 映射是否一致
            if (s_to_t.count(s_char) && s_to_t[s_char] != t_char) {
                return false;
            }

            // 检查 t -> s 映射是否一致
            if (t_to_s.count(t_char) && t_to_s[t_char] != s_char) {
                return false;
            }

            // 建立 s -> t 和 t -> s 的映射
            s_to_t[s_char] = t_char;
            t_to_s[t_char] = s_char;
        }

        return true; // 如果遍历完所有字符都没有冲突，则是同构的
    }
};

4.3.2 LC 219 存在重复元素II

问题描述

给你一个整数数组 nums 和一个整数 k，判断数组中是否存在两个 不同的索引 i 和 j，满足 nums[i] == nums[j] 且 abs(i - j) <= k。如果存在，返回 true；否则，返回 false。

思路分析

这道题是 LC 217 的扩展版，不仅要判断是否有重复元素，还要求这些重复元素的索引之差不超过给定的数字 k。我们可以使用哈希表记录每个数字的最后一次出现位置。当我们遍历数组时，遇到一个数字先检查字典中是否已经存在它：

1. 如果数字存在，检查它之前的索引和当前索引的差是否小于等于 k。如果满足条件，返回 true。
2. 如果不满足条件，更新该数字的最新出现位置。
3. 遍历完整个数组后，如果没有找到符合条件的数字，返回 false。

提示

• 在哈希表中记录每个数字的最后出现位置。
• 确保在检查时两个相同数字的索引差小于等于 k。

参考解答

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> pos;  // 记录每个数字最后一次出现的位置

        for (int i = 0; i < nums.size(); ++i) {
            if (pos.count(nums[i]) && i - pos[nums[i]] <= k) {
                return true;  // 如果找到满足条件的重复元素
            }
            pos[nums[i]] = i;  // 更新该数字的最新位置
        }

        return false;  // 如果没有找到符合条件的重复元素
    }
};

5 课后练习

频率统计

题目编号	题目名称	题目描述
LC 451	根据字符出现频率排序	给定一个字符串，请将字符按出现频率排序。
LC 692	前K个高频单词	给定一个单词列表，返回前 K 个出现频率最高的单词。
LC 347	前K个高频元素	给定一个整数数组，返回出现频率前 K 高的元素
LC 554	砌墙	计算通过一堵墙的垂直线段穿过的砖块数量最少的地方。
LC 2085	统计出现过一次的公共字符串	返回在两个字符串数组中都恰好出现一次的字符串的数目。

快速查找

题目编号	题目名称	题目描述
LC 594	最长和谐子序列	找到和谐子序列的最长长度，最大值和最小值相差为1。
LC 525	连续数组	给定一个二进制数组，找到长度相同的0和1的最长子数组。
LC 49	字母异位词分组	给定一个字符串数组，将字母异位词组合在一起。
LC 169	多数元素	给定一个大小为n的数组nums，返回其中的多数元素。
LC 409	最长回文串	给定一个字符串，返回其中可以构成的最长回文串的长度。

哈希映射

题目编号	题目名称	题目描述
LC 290	单词规律	给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。
LC 560	和为K的子数组	找出数组中和为 k 的连续子数组的个数。
LC 249	移位字符串分组	给定一个包含仅小写字母字符串的列表，将该列表中所有满足 “移位” 操作规律的组合进行分组并返回。
LC 953	验证外星语词典	给定一个外星词典的顺序表，判断一组单词是否按照这个外星词典的顺序排列。
LC 12	整数转罗马数字	给定一个整数，将其转换为罗马数字。