如何高效地从人员列表中找出完全包含于其中的所有朋友组

给定一组人员及两个工具函数（获取某人所属的组、获取某组包含的人员），需快速找出所有成员均在输入人员列表中的朋友组，避免低效的嵌套遍历与重复检查。

在处理“人员-群组”双向关联关系时，核心挑战在于：无法枚举全部群组，也无法预知群组总数，但又必须精准识别出那些“成员全部落在查询人员子集内”的群组（即群组是查询人员集合的子集）。原始方法对每个人员遍历其所属群组，并对每个群组调用 containsAll(group.getPersons())，时间复杂度高达 O(N × M × K)（N 为查询人数，M 为人均群组数，K 为平均群组大小），且 containsAll 在未优化集合上为线性扫描，性能瓶颈明显。

✅ 优化思路：哈希计数 + 子集判定

关键洞察是：一个群组 G 被完整包含于查询人员集合 S 中，当且仅当 G 中的每一位成员都属于 S。因此，我们无需反复检查整个群组列表是否被包含，而应：

1. 将查询人员列表转为高效查找结构（如 HashSet），使单次成员判断降为 O(1)；
2. 对每个“可能相关”的群组 G，统计其在 S 中实际出现的成员数量；
3. 若该数量等于 G 的总人数，则 G 完全包含于 S。

由于我们无法直接遍历所有群组，只能通过查询人员间接触达——即：所有候选群组，必然是至少一个查询人员所属的群组。因此，我们只需遍历每个查询人员的 getGroups()，收集所有“被提及”的群组，并对其做计数。

WOMBO

使用AI创作美丽的艺术品

下载

? 实现步骤（Java 示例）

import java.util.*;

public List findFullyContainedGroups(List queryPersons) {
    // Step 1: 构建查询人员的 O(1) 查找集合
    Set personSet = new HashSet<>(queryPersons);

    // Step 2: 统计每个候选群组在 personSet 中的实际成员数
    Map groupMemberCount = new HashMap<>();
    Map groupTotalSize = new HashMap<>(); // 缓存群组总人数，避免重复调用

    for (Person p : queryPersons) {
        for (Group g : p.getGroups()) {
            // 首次遇到该群组：缓存其总人数
            if (!groupTotalSize.containsKey(g)) {
                List allMembers = g.getPersons();
                groupTotalSize.put(g, allMembers.size());
                groupMemberCount.put(g, 0); // 初始化计数
            }

            // 若该人员确实在 personSet 中（必然成立，因 p ∈ queryPersons），则为其所属群组计数 +1
            if (personSet.contains(p)) {
                groupMemberCount.merge(g, 1, Integer::sum);
            }
        }
    }

    // Step 3: 筛选完全匹配的群组
    List result = new ArrayList<>();
    for (Map.Entry entry : groupMemberCount.entrySet()) {
        Group g = entry.getKey();
        int matchedCount = entry.getValue();
        int totalSize = groupTotalSize.get(g);
        if (matchedCount == totalSize && totalSize > 0) {
            result.add(g);
        }
    }

    return result;
}

⚠️ 注意事项与边界处理

• 去重保障：使用 Map 天然避免同一群组被重复添加，无需额外 personsTracked 列表；
• 空群组/无效群组：groupTotalSize.get(g) 为 0 时跳过，防止误判；
• 内存权衡：缓存 groupTotalSize 避免多次调用 g.getPersons().size()（若该方法开销大）；若 getPersons() 是轻量 getter，可改为运行时计算；
• 并发安全：若 getGroups() 或 getPersons() 非线程安全，需外部同步；
• 扩展性：该算法时间复杂度为 O(T)，其中 T 是“查询人员所属群组的总人次”（即所有 p.getGroups() 返回列表长度之和），空间复杂度为 O(G)（G 为涉及的不同群组数），已达到理论最优下界——因为至少需访问每条“人员∈群组”关系一次。

✅ 总结

该方案摒弃了暴力子集验证，转而采用增量计数 + 哈希查找策略，将核心判断从 O(K) 降至 O(1)，整体效率提升显著。它充分利用了问题约束（仅能通过人员触达群组），以最小必要访问完成精准筛选，是图论中“子图判定”思想在实际业务场景下的轻量级落地，适用于社交网络、权限分组、设备集群等类似关系建模场景。