Map 和 Set 在算法中的常见使用场景

在算法中，Map<类型, 类型> 和 Set<类型> 是非常常用的数据结构，它们各自有不同的优势和适用场景。以下是这两种数据结构在算法中的常见使用场景总结。

---

1. Map<类型, 类型> 在算法中的常见使用场景

Map 是一种存储键值对的数据结构，其中每个键对应一个唯一的值。Map 常用于需要按键访问值的场景，并且它支持快速的查找、插入和删除操作。

常见场景

1.1 计数问题

用于统计某个元素出现的次数，例如字符频率统计、单词频率统计、数字出现次数等。

示例：统计字符串中每个字符的出现次数

Map<Character, Integer> freqMap = new HashMap<>();
for (char c : str.toCharArray()) {freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
}

1.2 查找和存储映射关系

存储某个键到多个值的映射。例如图的邻接表表示、字母异位词分组、字符串搜索等。

示例：按字母异位词分组字符串

Map<String, List<String>> map = new HashMap<>();
for (String str : strs) {char[] chars = str.toCharArray();Arrays.sort(chars);String sorted = new String(chars);map.putIfAbsent(sorted, new ArrayList<>());map.get(sorted).add(str);
}

1.3 图的邻接表

用 Map 存储图的节点与其邻居的关系，特别适用于有向图或无向图。

示例：

Map<String, List<String>> graph = new HashMap<>();
graph.put("A", Arrays.asList("B", "C"));
graph.put("B", Arrays.asList("A", "D"));

1.4 动态规划中的状态存储

在动态规划中，可以使用 Map 来存储子问题的解，以便优化计算过程（例如记忆化搜索）。

示例：

Map<Integer, Integer> memo = new HashMap<>();
public int fib(int n) {if (n <= 1) return n;if (memo.containsKey(n)) return memo.get(n);memo.put(n, fib(n - 1) + fib(n - 2));return memo.get(n);
}

1.5 哈希表

Map 用于实现哈希表（如查找表），在处理需要快速查找的场景中非常高效。

1.6 集合中的去重与查找

用 Map 来保存已处理的元素，并通过键来确保唯一性。例如在一些组合问题中，可以避免重复计算。

---

2. Set<类型> 在算法中的常见使用场景

Set 是一种不允许重复元素的集合，常用于需要唯一性和集合运算的场景。它提供了高效的查找、插入和删除操作，并且没有顺序要求。Set 常用于以下算法场景：

常见场景

2.1 去重

用于去除集合或数组中的重复元素，尤其适合字符串、字符数组等。

示例：

Set<Character> uniqueChars = new HashSet<>();
for (char c : str.toCharArray()) {uniqueChars.add(c);
}

2.2 字符集合问题

用于处理字符串、字符集的操作，比如查找两个字符串的共同字符、字符的差异等。

示例：查找两个字符串的交集

Set<Character> set1 = new HashSet<>(Arrays.asList('a', 'b', 'c'));
Set<Character> set2 = new HashSet<>(Arrays.asList('b', 'c', 'd'));
set1.retainAll(set2);  // 求交集

2.3 集合运算

Set 提供了并集、交集、差集等集合运算，适用于需要集合运算的问题，比如图的连通性分析、社交网络分析等。

示例：并集操作

Set<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3));
Set<Integer> set2 = new HashSet<>(Arrays.asList(3, 4, 5));
set1.addAll(set2);  // 并集操作

2.4 图的遍历与连通性检测

在图算法（如 DFS、BFS）中，Set 常用于标记已访问的节点，避免重复访问。

示例：

Set<String> visited = new HashSet<>();
visited.add(node);  // 在图遍历时标记访问的节点

2.5 无重复字符子串问题

用于解决滑动窗口算法中的无重复字符的最长子串问题，通过 Set 来判断当前窗口中字符是否重复。

示例：

Set<Character> set = new HashSet<>();
int maxLength = 0, left = 0;
for (int right = 0; right < str.length(); right++) {while (set.contains(str.charAt(right))) {set.remove(str.charAt(left));left++;}set.add(str.charAt(right));maxLength = Math.max(maxLength, right - left + 1);
}

2.6 集合的判重

用 Set 来检测某个元素是否已经出现过，特别适用于需要重复检查的场景，如去除重复数字、去除重复字符串等。

---

总结

数据结构	常见使用场景
Map<类型, 类型>	1. 计数问题（如字符、单词频率统计） 2. 图的邻接表表示 3. 动态规划中的状态存储 4. 哈希表实现 5. 字符串或单词分组 6. 查找和存储映射关系
Set<类型>	1. 去重（去除重复元素） 2. 字符集合问题（交集、并集等） 3. 集合运算（交集、并集、差集） 4. 图的遍历（标记已访问节点） 5. 滑动窗口问题（无重复字符子串） 6. 判重（检查元素是否已出现过）

• Map 适用于需要存储键值对、快速查找、分组和映射的场景，如图、计数、状态存储等。
• Set 适用于需要唯一性、集合运算和去重的场景，如字符处理、滑动窗口问题、图算法中的节点访问标记等。

---