传统的经过两次循环讲相同的元素去除的时间复杂度为 O(M*N)数据结构
利用hash这种颇有用的数据结构来实现。咱们知道，hash的特色之一就是不容许有重复元素，即hash表中的元素都是惟一的。因此，咱们的思路就是：先把第一个集合的全部元素都放进hashSet中，时间复杂度O(M)；再把第二个集合中的元素放进hashSet中，若是有重复元素，就是这2个集合的交集，时间复杂度为O(N)。即总的时间复杂度从O(M*N)下降到了O(M+N)spa
public static List<string> GetIntersection2(List<string> list1, List<string> list2) { //第二种方法：hash List<string> list3 = new List<string>(); HashSet<string> hashSet = new HashSet<string>(); foreach (string item in list1) { hashSet.Add(item); } foreach (string item in list2) { if (hashSet.Add(item) == false) { list3.Add(item); } } return list3; }