高效的从两个List中找到重复元素

从两个list中找到重复元素，很容易就想到两个for循环嵌套来实现，但是如果两个list都非常大的话，时间复杂度将非常大。所以这里介绍一种以空间换时间的方法。
1.因为list中是可以存在相同元素的，但是想以2来得到重复的元素，所以需要进行去重
2.将list中的元素放入map中，并对元素个数进行一个统计
3.将hashmap中value为2的key存入list

代码实现：

public class TestList {
    public static void main(String[] args) {
        List<String> list1 = new ArrayList<String>();
        List<String> list2 = new ArrayList<String>();

        list1.add("a");
        list1.add("b");
        list1.add("b");
        list1.add("c");

        list2.add("b");
        list2.add("c");
        list2.add("d");

        String duplicate = findDuplicate(list1, list2);
        System.out.println("duplicate element: " + duplicate);
    }

    private static String findDuplicate(List<String> list1, List<String> list2) {
        List<String> duplicate = new ArrayList<String>();
        Map<String, Integer> map = new HashMap<String, Integer>();
        //1.去重
        List<String> list3 = new ArrayList<String>(new HashSet<String>(list1));
        List<String> list4 = new ArrayList<String>(new HashSet<String>(list2));
        //2.将list中的元素加入map中并进行统计
        for (String s1 : list3) {
            map.put(s1, 1);
        }
        //3.将list中的元素加入map中并进行统计
        for (String s2 : list4) {
            map.put(s2, (map.get(s2) == null ? 1 : 2));
        }
        //4.将重复的元素放入list中
        for (Map.Entry<String, Integer> m : map.entrySet()) {
            if (m.getValue() == 2) {
                duplicate.add(m.getKey());
            }
        }
        return duplicate.toString();
    }
}

hashmap的get方法效率也是很高的