如何判断一个String列表是否为另一个String列表的子集（忽略顺序）

场景说明 #

你需要判断一个String列表是否是另一个父列表的子集，且不考虑元素顺序，例如：

• 父列表：{"abc", "def", "ghi", "xyz"}
• 子列表1{"def", "abc"} → 是子集
• 子列表2{"1234", "ghi"} → 不是子集（"1234"不存在）
• 子列表3{"ghi", "xyz", "abc"} → 是子集

你之前使用的Collections.indexOfSubList(parentDataList, child1) != -1会检查连续且顺序一致的子序列，不符合无顺序的需求，以下是两种适配方案：

方案1：无重复元素场景（高效简洁） #

如果父列表和子列表中都没有重复元素，直接将列表转换为Set，利用Set的无序性和containsAll方法判断：

List<String> parentDataList = Arrays.asList("abc", "def", "ghi", "xyz");
List<String> child1 = Arrays.asList("def", "abc");

Set<String> parentSet = new HashSet<>(parentDataList);
Set<String> childSet = new HashSet<>(child1);

// 判断子Set的所有元素都存在于父Set中
boolean isSubset = parentSet.containsAll(childSet);

该方法时间复杂度为O(n)（n为父列表长度），因为HashSet的contains操作是常数时间。

方案2：存在重复元素场景（精准计数） #

如果列表中存在重复元素（例如父列表是{"a","a","b"}，子列表{"a","a"}是子集，但{"a","a","a"}不是），需要统计每个元素的出现次数，确保子列表的元素计数不超过父列表：

List<String> parentDataList = Arrays.asList("a", "a", "b", "c");
List<String> childList = Arrays.asList("a", "a");

// 统计父列表元素出现次数
Map<String, Integer> parentCountMap = new HashMap<>();
for (String s : parentDataList) {
    parentCountMap.put(s, parentCountMap.getOrDefault(s, 0) + 1);
}

boolean isSubset = true;
for (String s : childList) {
    int currentCount = parentCountMap.getOrDefault(s, 0);
    if (currentCount == 0) {
        isSubset = false;
        break;
    }
    // 每匹配一个元素，父列表计数减1
    parentCountMap.put(s, currentCount - 1);
}

该方法会严格校验元素的出现次数，适用于有重复元素的场景。

内容的提问来源于stack exchange，提问作者mattsmith5