在面试的时候，有一道编程题，最后的解决办法想到了使用交集差集去解决。
自己的解决办法很传统，双层循环，list1的每个值和list2的每个值都去比较一下，这样的时间复杂度太高O（m*n）
面试官也提出了这个问题。

想想还有什么方法能够优化一下，思路是这样的：
定义一个map存放lsit，key为lsit1的各个元素，value为该元素出现的次数
把list2的所有元素也放到map里，如果已经存在则value加1
最后根据map里value的值去判断交集和差集
这样我们只需循环m+n次，时间复杂度为O（m+n）

代码如下：

public class Demo {
  
  public static void main(String[] args) {
    List<String> list1 = new ArrayList<String>();
    list1.add("s");
    list1.add("e");
    list1.add("a");
    list1.add("d");
    list1.add("d");
    list1.add("f");
    list1.add("v");
    list1.add("c");
    list1.add("r");
    list1.add("c");
    
    List<String> list2 = new ArrayList<String>();
    list2.add("s");
    list2.add("c");
    list2.add("a");
    list2.add("v");
    list2.add("k");
    list2.add("p");
    list2.add("v");
    list2.add("c");
    list2.add("r");
    list2.add("c");
    
    // s,e,a,d,d,f,v,c,r,c
    // s,c,a,v,k,p,v,c,r,c
    // 交集：s,a,v,c,r
    // 差集：e,d,f,k,p
    
    List<String> alist = Demo.intersection(list1, list2);
    for (String string : alist) {
      System.out.print(string + " ");
    }
    
    System.out.println();
    List<String> blist = Demo.subtraction(list1, list2);
    for (String string : blist) {
      System.out.print(string + " ");
    }
  }
  
  /**
   * 求两个集合的交集
   * 
   * @param list1
   * @param list2
   */
  public static List<String> intersection(List<String> list1, List<String> list2) {
    List<String> result = new ArrayList<String>();
    Iterator<Map.Entry<String, Integer>> itor = calculationFront(list1, list2);
    
    while (itor.hasNext()) {
      Map.Entry<String, Integer> entry = itor.next();
      Integer tmp = entry.getValue();
      if (tmp > 1) {
        result.add(entry.getKey());
      }
    }
    
    return result;
  }
  
  /**
   * 求两个集合的差集
   * 
   * @param list1
   * @param list2
   * @return
   */
  public static List<String> subtraction(List<String> list1, List<String> list2) {
    List<String> result = new ArrayList<String>();
    Iterator<Map.Entry<String, Integer>> itor = calculationFront(list1, list2);
    
    while (itor.hasNext()) {
      Map.Entry<String, Integer> entry = itor.next();
      Integer tmp = entry.getValue();
      if (tmp == 1) {
        result.add(entry.getKey());
      }
    }
    
    return result;
  }
  
  /**
   * 运算前置
   * 
   * @param list1
   * @param list2
   * @return
   */
  public static Iterator<Map.Entry<String, Integer>> calculationFront(List<String> list1,
                                                                      List<String> list2) {
    Map<String, Integer> map = new HashMap<String, Integer>();
    List<String> maxList = list1;
    List<String> minList = list2;
    if (list2.size() > list1.size()) {
      maxList = list2;
      minList = list1;
    }
    
    for (String str : maxList) {
      map.put(str, 1);
    }
    
    for (String str : minList) {
      Integer num = map.get(str);
      if (null != num) {
        map.put(str, ++num);
        continue;
      }
      map.put(str, 1);
    }
    
    return map.entrySet().iterator();
  }
}

还有更快的方法吗？
nutz.cn 貌似还没有这样的帖子吧
@全体