4. 字典 Map 在算法题中怎么用

字典或 Map 是手撕代码中最常用的辅助数据结构之一。Python 中叫 dict，Java 中常用 HashMap。它的核心价值是用空间换时间，把原本需要双层循环查找的问题，优化成一次遍历。测试岗面试中，Map 常用于两数之和、字符频次统计、数组去重、找重复元素、找第一个不重复字符、分组统计等题型。

对测试工程师来说，Map 也非常贴近日常工作。接口请求参数、Header、响应 JSON、配置项、数据库字段，都可以用键值对表达。因此 Map 题不仅是算法基础，也和测试自动化数据处理高度相关。

一、Map 适合解决什么问题

看到下面关键词，可以优先想到 Map：

是否出现过；
出现几次；
快速查找；
根据 key 找 value；
统计频次；
去重；
分组；
两个值是否匹配。

Map 的平均查找复杂度通常是 O(1)，所以可以提升效率。

二、两数之和

这是 Map 最经典应用。

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        need = target - num
        if need in seen:
            return [seen[need], i]
        seen[num] = i
    return []

思路：遍历当前数时，检查补数是否已经出现。

复杂度：时间 O(n)，空间 O(n)。

三、字符频次统计

def count_chars(s):
    counter = {}
    for ch in s:
        counter[ch] = counter.get(ch, 0) + 1
    return counter

适合判断重复字符、统计日志关键字、比较两个字符串字符组成。

四、找第一个不重复字符

def first_unique_char(s):
    counter = {}
    for ch in s:
        counter[ch] = counter.get(ch, 0) + 1
    for i, ch in enumerate(s):
        if counter[ch] == 1:
            return i
    return -1

注意第二次遍历要按原字符串顺序，否则找不到“第一个”。

五、数组去重

如果只需要去重，可以用 Set；如果要统计次数，用 Map。

def count_nums(nums):
    counter = {}
    for num in nums:
        counter[num] = counter.get(num, 0) + 1
    return counter

如果需要找出现次数最多的数字，也可以基于这个 Map。

六、分组问题

例如按字符串长度分组：

def group_by_length(words):
    result = {}
    for word in words:
        key = len(word)
        if key not in result:
            result[key] = []
        result[key].append(word)
    return result

Java 中类似 Map<Integer, List<String>>。

七、Map 在接口自动化中的类比

接口自动化中：

headers = {"Authorization": "Bearer token"}
payload = {"username": "tester", "password": "123456"}
response = {"code": 0, "message": "success"}

这些本质都是 key-value。算法题中的 Map 能力，会直接迁移到测试数据处理。

八、Map 使用常见坑

1. key 不存在

Python 可以用 get 避免 KeyError：

counter[ch] = counter.get(ch, 0) + 1

Java 中要注意 map.get(key) 可能返回 null。

2. 覆盖旧值

同一个 key 赋值多次，后面的会覆盖前面的。

3. 不保证顺序

Python 现代版本 dict 保持插入顺序，但算法题不要过度依赖。Java HashMap 不保证顺序。

4. 空间复杂度

Map 提高速度，但会占用额外空间。

九、Java 写法参考

Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
    int need = target - nums[i];
    if (map.containsKey(need)) {
        return new int[]{map.get(need), i};
    }
    map.put(nums[i], i);
}
return new int[]{};

测试开发面试中，如果你用 Java，就要熟悉 put、get、containsKey。

十、面试回答模板

如果面试官问“字典 Map 在算法题中怎么用”，可以这样回答：

Map 主要用于快速查找和统计频次。遇到是否出现过、出现几次、根据值找下标、去重统计这类题，我会优先考虑 Map。比如两数之和，用 Map 保存已遍历数字和下标，遍历当前数时检查 target - num 是否存在，可以把时间复杂度从 O(n²) 优化到 O(n)。字符频次统计、找第一个不重复字符、数组重复元素也都可以用 Map。使用时要注意 key 不存在、重复 key 覆盖和空间复杂度。

十一、练习清单

两数之和；
字符频次统计；
第一个不重复字符；
数组元素计数；
找重复数字；
找出现次数最多元素；
判断异位词；
分组字符串；
用 Java HashMap 写两数之和；
准备 Map 面试表达。

Map 是手撕代码高频工具。掌握它，可以解决很多查找、统计和去重类问题。

配套刷题：

手撕代码