本文介绍一种基于哈希映射的线性时间算法，用于在无法遍历全部群组的前提下，快速找出所有成员均来自给定人员子集的群组，避免重复调用低效的 `containsall` 操作。
在实际系统（如社交网络、班级关系管理或权限分组）中，我们常面临一类典型问题：已知一组人员（如 [P1, P3, P2, P4]），以及两个受限访问接口——getGroups(person) 返回该人所属的所有群组，getPersons(group) 返回该群组内的全部成员；但无法枚举所有群组或所有人员。目标是高效找出所有“被完全覆盖”的群组：即群组内每个成员都落在输入人员列表中。
原始方法（对每个人员遍历其所属群组，并对每个群组调用 personsTracked.containsAll(group.getPersons())）存在严重性能瓶颈：containsAll 在未排序列表上平均时间复杂度为 O(m×n)（m 为群组大小，n 为输入人员数），嵌套循环后整体可达 O(k·g·n)（k 为总人员-群组关联数，g 为平均群组大小），极易成为性能瓶颈。
✅ 优化核心思想：计数替代全量校验
不逐个比对群组成员是否都在输入集合中，而是采用两阶段计数策略：
- 预处理输入人员集合：将查询人员列表转为 HashSet<Person>，实现 O(1) 成员查找；
-
按群组维度统计覆盖度：
- 使用 Map<Group, Integer> 记录每个群组在当前输入人员中实际出现的成员数（初始为 0）；
- 使用 Map<Group, Integer>（或复用同一 Map）预先记录每个群组的总人数（可懒加载或预缓存）；
- 单次遍历所有“关联边”：对每个输入人员 p，调用 getGroups(p) 获取其所属群组列表；对每个群组 g，执行 countMap.merge(g, 1, Integer::sum)；
- 筛选完全匹配群组：遍历 countMap，若 countMap.get(g) == totalSizeMap.get(g)，则 g 是目标群组。
该算法时间复杂度为 O(K)，其中 K 是输入人员与其所属群组的总关联数（即所有 getGroups(p) 返回结果的长度之和），空间复杂度为 O(G')（G' 为至少有一个成员在输入列表中的群组数量）。
以下是 Java 示例实现（假设 Person 和 Group 为不可变对象，且已正确实现 equals()/hashCode()）：
import java.util.*;
public List<Group> findFullyContainedGroups(List<Person> queryPersons) {
// Step 1: 构建人员快速查找集
Set<Person> personSet = new HashSet<>(queryPersons);
// Step 2: 统计每个相关群组在 queryPersons 中的成员出现次数
Map<Group, Integer> groupMemberCount = new HashMap<>();
Map<Group, Integer> groupTotalSize = new HashMap<>(); // 可选：若未预缓存，则首次访问时计算
// Step 3: 遍历每个查询人员及其所属群组
for (Person p : queryPersons) {
for (Group g : getGroups(p)) {
// 懒加载群组总人数（仅首次访问该群组时触发）
groupTotalSize.computeIfAbsent(g, grp -> getPersons(grp).size());
// 累加当前人员对该群组的“覆盖贡献”
groupMemberCount.merge(g, 1, Integer::sum);
}
}
// Step 4: 收集完全覆盖的群组
List<Group> result = new ArrayList<>();
for (Map.Entry<Group, Integer> entry : groupMemberCount.entrySet()) {
Group g = entry.getKey();
int covered = entry.getValue();
int total = groupTotalSize.get(g);
if (covered == total) {
result.add(g);
}
}
return result;
}⚠️ 注意事项与增强建议：
- 哈希一致性：确保 Group 类正确重写 equals() 和 hashCode()，否则 HashMap 将无法正确索引；
- 内存权衡：若群组总数极大但单次查询涉及群组较少，此方案显著优于暴力法；若需高频查询，可预构建 Group → totalSize 全局缓存；
- 去重保障：因使用 Map 聚合，天然避免重复添加同一群组；
- 扩展性：该模型易于扩展支持“部分覆盖”（如 ≥80% 成员在列表中）或加权群组匹配。
总结：通过将“集合包含判断”转化为“计数匹配”，我们把原算法的二次方级开销降为线性，同时保持逻辑清晰、代码简洁，是处理受限访问图结构查询的经典范式。
