电面面经一枚 顺带求人品

fsd123 发表于 2015-12-19 14:11
啊，是的。确实过不了这个 case ，那就修改下移动策略

初始化 slow 和 fast 为 head，进入循环，判定  ...

不过你这个方法要每次拷贝set， 当指针移动的时候， 时间应该还是o(mn)

xiaomiaoaoao 发表于 2015-12-19 16:32
不过你这个方法要每次拷贝set， 当指针移动的时候， 时间应该还是o(mn)

为什么要拷贝 set ？就算最后要维护 set 不变，返回前再将元素加进 set 就好。

而且时间是 O(n) 啊，slow 和 fast 都只遍历 list 一次

能不能不在set上操作， 用hashMap记录visited, fast指向的元素 !visited && in set 就继续走，如果slow fast间距离达到set的size就说明找到了； 否则，看是因为什么fail的：如果是因为visited,就移动slow, 等slow经过重复的元素就停，继续移动fast; 如果是因为遇到了set里没有的元素，就slow和fast都指向后面的元素

O(n^2) 和 O(n) 不知道有没问题。祝楼主顺利拿到Onsite~!! 求大家指导代码，谢谢！

        public static boolean subList(HashSet<Integer> set,int[] nums){

                if(set==null || nums ==null) return false;

                int left = 0,right=0;

                HashSet<Integer> visited = new HashSet<Integer>();

                for(;right<nums.length;right++){

                        if(!set.contains(nums[right])){

                                visited.clear();

                                continue;

                        }else{

                                if(visited.contains(nums[right])){

                                        while(left<right && nums[left]!=nums[right]){

                                                visited.remove(nums[left]);

                                                left++;

                                        }

                                        left++;

                                }else{

                                        visited.add(nums[right]);

                                        if(visited.size()==set.size()) return true;

                                }

                        }

                }

                return false;

        }

O(n^2)

1.         public static boolean subListExist(HashSet<Integer> set, int[] nums){
   
2.                 if(set==null || nums ==null) return false;
   
3.                 for(int i=0;i<nums.length;i++){
   
4.                         HashSet<Integer> found = new HashSet<Integer>();
   
5.                         for(int j=i;j<i+set.size();j++){
   
6.                                 if(!set.contains(nums[j])){
   
7.                                         break;
   
8.                                 }else{
   
9.                                         if(found.contains(nums[j])){
   
10.                                                 break;
    
11.                                         }else{
    
12.                                                 found.add(nums[j]);
    
13.                                         }
    
14.                                 }
    
15.                         }
    
16.                         if(found.size()==set.size()) return true;
    
17.                 }
    
18.                 return false;
    
19.         }

复制代码

写了下代码，时间和空间复杂度都是O(n)，其实这个题就是sliding window

1. public class SublistEqualsSet {
   
2. 
   
3.         public static boolean isSublistEqualsSet(List<Integer> list,
   
4.                         Set<Integer> set) {
   
5.                 if (set == null || list == null) {
   
6.                         return false;
   
7.                 }
   
8.                 if (set.size() == 0) {
   
9.                         return true;
   
10.                 }
    
11.                 if (list.size() == 0) {
    
12.                         return false;
    
13.                 }
    
14.                 int start = 0;
    
15.                 int pos = 0;
    
16.                 System.out.println(set.size());
    
17.                 Set<Integer> tmp = new HashSet<Integer>();
    
18.                 while (pos < list.size()) {
    
19.                         int cur = list.get(pos);
    
20.                         if (set.contains(cur)) {
    
21.                                 while (start < pos && tmp.contains(cur)) {
    
22.                                         tmp.remove(list.get(start));
    
23.                                         start++;
    
24.                                 }
    
25.                                 tmp.add(cur);
    
26.                                 if (tmp.size() == set.size()) {
    
27.                                         return true;
    
28.                                 }
    
29.                         } else {
    
30.                                 start = pos + 1;
    
31.                                 tmp.clear();
    
32.                         }
    
33.                         pos++;
    
34.                 }
    
35. 
    
36.                 return false;
    
37.         }
    
38. 
    
39.         public static void main(String[] args) {
    
40.                 List<Integer> list = new ArrayList<Integer>(
    
41.                                 Arrays.asList(1, 2, 3, 2, 4, 1));
    
42.                 Set<Integer> set = new HashSet<Integer>();
    
43.                 set.add(1);
    
44.                 set.add(2);
    
45.                 set.add(3);
    
46.                 set.add(4);
    
47.                 System.out.println(isSublistEqualsSet(list, set));
    
48.         }
    
49. }

复制代码

Sliding Window. 正解是O(n)时间和O(n)空间 hashset