fb onsite 这样“黑”的我真的很不舒服

mysteryjoe 发表于 2016-10-28 10:38
4sum average应该没有n2logn的吧，看过很多自称n2logn的方法，分析都是至少n3的

理论上O(n^2)可以做，把所有(x,y) pair的和放到hash table里面，看有没有两个pair加起来是target。K sum的理论复杂度是O(n^(K+1)/2)

楼主能具体说说设计题那道怎么做的吗，谢谢！

写了下代码

1. public class Four4SumFastest {
   
2. 
   
3.     class Pair {
   
4.         int i;
   
5.         int j;
   
6.         int sum;
   
7.         public Pair(int i, int j, int sum) {
   
8.             this.i = i;
   
9.             this.j = j;
   
10.             this.sum = sum;
    
11.         }
    
12.     }
    
13. 
    
14.     public List<int[]> findFourElements(int[] arr, int k) {
    
15.         List<int[]> res = new ArrayList<>();
    
16.         if (arr == null || arr.length < 4) {
    
17.             return res;
    
18.         }
    
19. 
    
20.         int n = arr.length;
    
21.         Arrays.sort(arr);
    
22.         List<Pair> list = new ArrayList<>();
    
23.         for (int i = 0; i < n - 1; i ++) {
    
24.             for (int j = i + 1; j < n; j++) {
    
25.                 list.add(new Pair(i, j, arr[i] + arr[j]));
    
26.             }
    
27.         }
    
28. 
    
29.         Collections.sort(list, new Comparator<Pair>() {
    
30.             public int compare(Pair p1, Pair p2) {
    
31.                 return p1.sum - p2.sum;
    
32.             }
    
33.         });
    
34.         
    
35.         int i = 0;
    
36.         int j = list.size() - 1;
    
37.         HashSet<String> set = new HashSet<>();
    
38.         while (i < j) {
    
39.             int sum = list.get(i).sum + list.get(j).sum;
    
40.             if (sum == k && nonCommon(list.get(i), list.get(j))) {
    
41.                 int[] tmp = new int[4];
    
42.                 tmp[0] = arr[list.get(i).i];
    
43.                 tmp[1] = arr[list.get(i).j];
    
44.                 tmp[2] = arr[list.get(j).i];
    
45.                 tmp[3] = arr[list.get(j).j];
    
46.                 Arrays.sort(tmp);
    
47.                 String key = tmp[0] + " " + tmp[1] + " " + tmp[2] + " " + tmp[3];
    
48.                 if (!set.contains(key)) {
    
49.                     res.add(new int[] {arr[list.get(i).i], arr[list.get(i).j], arr[list.get(j).i], arr[list.get(j).j]});
    
50.                     set.add(key);
    
51.                 }
    
52.                 i++;
    
53.                 j--;
    
54.             } else if (sum > k) {
    
55.                 j--;
    
56.             } else {
    
57.                 i++;
    
58.             }
    
59.         }
    
60. 
    
61.         return res;
    
62.     }
    
63. 
    
64.     private boolean nonCommon(Pair p1, Pair p2) {
    
65.         if (p1.i == p2.i || p1.i == p2.j || p1.j == p2.j || p1.j == p2.i) {
    
66.             return false;
    
67.         }
    
68. 
    
69.         return true;
    
70.     }
    
71. 
    
72.     public static void main(String[] args) {
    
73.         int[] arr = {10, 2, 3, 4, 5, 9, 7, 8, 7, 8, 2, 2, 7, 7};
    
74.         Four4SumFastest f = new Four4SumFastest();
    
75.         List<int[]> res = f.findFourElements(arr, 23);
    
76.         for (int[] tmp : res) {
    
77.             String key = tmp[0] + " " + tmp[1] + " " + tmp[2] + " " + tmp[3];
    
78.             System.out.println(key);
    
79.         }
    
80.     }
    
81. }

复制代码

bigbearlake 发表于 2017-4-26 11:57
写了下代码

我去。。。这一会就得写这么多代码啊。。。