94-集合面试题分析

面试题如下：

面试官问：

有集合A和集合B，现在需要将两个集合中重复的元素放入到集合C中，请问你会怎么编程实现？

这道题，简单想到的是循环遍历两个集合A和B，然后将重复的元素放入到集合C中，我们来看看怎么实现？

List<String> list1 = Arrays.asList("a","b","c");
List<String> list2 = Arrays.asList("a","b");
List<String> list3 = new ArrayList<>();

for (String a : list1) {
    for (String b : list2) {
        if(a.equals(b)){
            list3.add(a);
        }
    }
}
System.out.println(list3);

上述这个方案好吗？

我们先直观分析下，假设两个集合都是存放100个元素，那么就需要100*100，比较10000次，然后从时间复杂度来分析，时间复杂度为O(n²)。

那么，我们可以怎么优化？

来看看，一个时间复杂度为O(n)的写法

Set<String> set = new HashSet<>();
for (String a : list1) {
    set.add(a);
}
for (String b : list2) {
    if(set.contains(b)){
        list3.add(b);
    }
}
System.out.println(list3);