Java7中优雅获取所有子列表共有的字符串（替代四重循环）

嘿，我懂你现在的困扰——用四重循环来找出所有子列表都共有的字符串，不仅写起来麻烦，读起来头疼，效率还不高。既然要兼容Java 7不能用Stream，咱们可以利用Java集合的内置方法来实现更简洁优雅的方案，核心思路就是求多个集合的交集，具体来说是这样的：

核心思路 #

要找所有子列表都出现的字符串，本质上就是求所有子列表的交集。我们可以：

1. 以第一个子列表的元素作为初始的「候选共同元素集合」
2. 依次将这个候选集合和后续每个子列表求交集，逐步缩小范围
3. 最后剩下的元素就是所有子列表都包含的字符串

这种方法不仅避免了嵌套循环，还利用了Set的高效查找特性，比四重循环的效率高得多。

完整实现代码 #

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;

public class CommonElementsFinder {
    public static ArrayList<String> findCommonStrings(ArrayList<ArrayList<String>> names) {
        // 处理边界情况：输入为空，或者存在空的子列表，直接返回空结果
        if (names == null || names.isEmpty()) {
            return new ArrayList<>();
        }
        for (ArrayList<String> subList : names) {
            if (subList == null || subList.isEmpty()) {
                return new ArrayList<>();
            }
        }

        // 用LinkedHashSet可以保留元素在第一个子列表中的顺序，用HashSet则更高效（不关心顺序时选这个）
        Set<String> commonElements = new LinkedHashSet<>(names.get(0));

        // 遍历剩余子列表，逐步求交集
        for (int i = 1; i < names.size(); i++) {
            ArrayList<String> currentSubList = names.get(i);
            Set<String> currentSet = new HashSet<>(currentSubList);
            
            // 求交集：只保留同时存在于currentSet中的元素
            commonElements.retainAll(currentSet);

            // 提前终止优化：如果交集已经为空，没必要继续循环了
            if (commonElements.isEmpty()) {
                break;
            }
        }

        // 把Set转换为ArrayList返回，符合需求的数据结构
        return new ArrayList<>(commonElements);
    }

    // 测试用例
    public static void main(String[] args) {
        ArrayList<ArrayList<String>> names = new ArrayList<>();
        
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("Alice");
        list1.add("Bob");
        list1.add("Charlie");
        names.add(list1);

        ArrayList<String> list2 = new ArrayList<>();
        list2.add("Bob");
        list2.add("Charlie");
        list2.add("David");
        names.add(list2);

        ArrayList<String> list3 = new ArrayList<>();
        list3.add("Bob");
        list3.add("Charlie");
        names.add(list3);

        ArrayList<String> result = findCommonStrings(names);
        System.out.println(result); // 输出 [Bob, Charlie]
    }
}

代码说明 #

• 边界处理：先排除空输入或包含空子列表的情况——只要有一个子列表为空，就不可能存在共同元素，直接返回空列表。
• 集合选择：
  • 用LinkedHashSet初始化可以保留元素在第一个子列表中的顺序；如果不关心顺序，用HashSet会更高效。
  • 把每个子列表转成Set是因为Set的contains操作是O(1)时间复杂度，比ArrayList的O(n)快很多，能提升整体效率。
• 提前终止：如果中途交集变成空，直接跳出循环，避免不必要的计算。
• 结果转换：最后把Set转回ArrayList，符合你需求的数据结构。

和四重循环的对比 #

这个方案的时间复杂度是O(n*m)（n是子列表数量，m是子列表平均元素数），而你的四重循环是O(n²*m²)，效率提升非常明显，而且代码逻辑清晰，维护起来也容易。

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