FB热乎跪经

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

楼主这个是第一轮么？

1. import java.util.*;
   
2. 
   
3. public class Test {
   
4.     class Num {
   
5.         int val;
   
6.         int index;
   
7.         int flag;
   
8.         Num(int d, int i, int f) {
   
9.             this.val = d;
   
10.             this.index = i;
    
11.             this.flag = f;
    
12.         }
    
13.     }
    
14. 
    
15.     public void print(int[] nums) {
    
16.         if (nums == null || nums.length < 4) {
    
17.             return;
    
18.         }
    
19. 
    
20.         int n = nums.length;
    
21.         List<Num> lists = new ArrayList<>(2 * n);
    
22. 
    
23.         for (int i = 0; i < n; i++) {
    
24.             lists.add(new Num(nums[i], i, 1));
    
25.             if (nums[i] != 0)
    
26.                 lists.add(new Num(-1 * nums[i], i, -1));
    
27.         }
    
28. 
    
29.         Collections.sort(lists, new Comparator<Num>(){
    
30.             public int compare(Num n1, Num n2) {
    
31.                 if (n1.val == n2.val) {
    
32.                     return n1.index - n2.index;
    
33.                 }
    
34. 
    
35.                 return n1.val - n2.val;
    
36.             }
    
37.         });
    
38. 
    
39. 
    
40.         int len = lists.size();
    
41.         for (int i = 0; i < len - 3; i++) {
    
42.             if (lists.get(i).val + lists.get(i + 1).val + lists.get(i + 2).val + lists.get(i + 3).val > 0)
    
43.                 break;
    
44.             if (lists.get(i).val + lists.get(len - 1).val + lists.get(len - 2).val + lists.get(len - 3).val < 0)
    
45.                 continue;
    
46. 
    
47.             for (int j = i + 1; j < len - 2; j++) {
    
48.                 if (lists.get(i).val + lists.get(j).val + lists.get(j + 1).val + lists.get(j + 2).val > 0)
    
49.                     break;
    
50.                 if (lists.get(i).val + lists.get(j).val + lists.get(len - 1).val + lists.get(len - 2).val < 0)
    
51.                     continue;
    
52.                 int left = j + 1, right = len - 1;
    
53.                 while (left < right) {
    
54.                     if (lists.get(i).val + lists.get(j).val + lists.get(left).val + lists.get(right).val == 0) {
    
55.                         printRes(i, j, left++, right--, lists);
    
56.                     } else if (lists.get(i).val + lists.get(j).val + lists.get(left).val + lists.get(right).val < 0) {
    
57.                         left++;
    
58.                     } else {
    
59.                         right--;
    
60.                     }
    
61.                 }
    
62.             }
    
63.         }
    
64.     }
    
65. 
    
66.     private void printRes(int i1, int i2, int i3, int i4, List<Num> lists) {
    
67.         List<Num> res = new ArrayList<>(4);
    
68.         res.add(lists.get(i1));
    
69.         res.add(lists.get(i2));
    
70.         res.add(lists.get(i3));
    
71.         res.add(lists.get(i4));
    
72.         
    
73.         Set<Integer> visited = new HashSet<>();
    
74.         int flagSum = 0;
    
75.         for (Num n : res) {
    
76.             flagSum += n.flag;
    
77.             visited.add(n.index);
    
78.         }
    
79. 
    
80.         if (flagSum != 0 || visited.size() != 4)
    
81.             return;
    
82. 
    
83.         Collections.sort(res, new Comparator<Num>(){
    
84.             public int compare(Num n1, Num n2) {
    
85.                 if (n1.flag == n2.flag)
    
86.                     return n1.index - n2.index;
    
87. 
    
88.                 return n1.flag - n2.flag;
    
89.             }
    
90.         });
    
91. 
    
92.         if (res.get(0).index > res.get(2).index)
    
93.             return;
    
94. 
    
95.         System.out.println("Print index");
    
96.         System.out.println(res.get(0).index+"+"+res.get(1).index+"="+res.get(2).index+"+"+res.get(3).index);
    
97.         System.out.println("Print val");
    
98.         System.out.println(-res.get(0).val+"+"+-res.get(1).val+"="+res.get(2).val+"+"+res.get(3).val);
    
99.         
    
100.         // System.out.println(lists.get(i2).index+"+"+lists.get(i1).index+"="+lists.get(i3).index+"+"+lists.get(i4).index);
     
101.         // System.out.println(lists.get(i1).index+"+"+lists.get(i2).index+"="+lists.get(i4).index+"+"+lists.get(i3).index);
     
102.         // System.out.println(lists.get(i2).index+"+"+lists.get(i1).index+"="+lists.get(i4).index+"+"+lists.get(i3).index);
     
103.         System.out.println("");
     
104.     }
     
105. 
     
106.     public static void main(String args[]){
     
107.         Test test = new Test();
     
108.         int[] nums = new int[]{1,2,3,4,5,6};
     
109.         test.print(nums);
     
110.     }
     
111. }
     

复制代码

java版，欢迎指正。
我觉得代码应该只适用于数字都不重复的情况

yitati 发表于 2017-10-9 01:44
楼主这个是第一轮么？

是第一轮 字数

我觉得O(n^3)次是可行的，即使不排序，分别去第一个数的index i和第二个数的index j， index j之后用 hashmap那种做法解一个two sum，得到的一组4个数字，就可以排列出结果实现了ABCD BACD ABDC BADC

或者在数组里枚举分割线，左边枚举pair 右边枚举pair 遇到sum 相等，就输出排列。

没想到n^2该怎么写。哪位大神不吝赐教。

@wstjpu 的方法, O(n^3)

1.    
   
2. public List<int[]> find(int[] nums) {
   
3.         int n = nums.length;
   
4.         List<int[]> res = new ArrayList<>();
   
5.         Map<Integer, int[]> resmap = new HashMap<>();
   
6.         for (int i = 0; i < n; i ++) {
   
7.             for (int j = i + 1; j < n; j++) {
   
8.                 int sum = nums[i] + nums[j];
   
9.                 Map<Integer, List<Integer>> map = new HashMap<>();
   
10.                 for (int k = i + 1; k < n; k++) {
    
11.                     if (k == i || k == j) {
    
12.                         continue;
    
13.                     }
    
14.                     List<Integer> idxes = map.get(sum - nums[k]);
    
15.                     if (idxes != null) {
    
16.                         for (int idx :idxes) {
    
17.                             addPairs(resmap, new int[]{i, j, k, idx});
    
18.                         }
    
19.                     }
    
20.                     List<Integer> currIdxes = map.get(nums[k]);
    
21.                     if (currIdxes == null) {
    
22.                         currIdxes = new ArrayList<>();
    
23.                         map.put(nums[k], currIdxes);
    
24.                     }
    
25.                     currIdxes.add(k);
    
26.                 }
    
27.             }
    
28.         }
    
29.         return new ArrayList<>(resmap.values());
    
30.     }
    
31. 
    
32.     private void addPairs(Map<Integer, int[]> resmap, int[] pair) {
    
33.         int[] p1 = new int[]{pair[1], pair[0], pair[2], pair[3]};
    
34.         int[] p2 = new int[]{pair[1], pair[0], pair[3], pair[2]};
    
35.         int[] p3 = new int[]{pair[0], pair[1], pair[3], pair[2]};
    
36. 
    
37.         resmap.put(Arrays.hashCode(pair), pair);
    
38.         resmap.put(Arrays.hashCode(p1), p1);
    
39.         resmap.put(Arrays.hashCode(p2), p2);
    
40.         resmap.put(Arrays.hashCode(p3), p3);
    
41.     }

复制代码

感觉用标准4sum的方法可以做到N^3，N^2实在想不到了

wstjpu 发表于 2017-10-12 06:02
我觉得O(n^3)次是可行的，即使不排序，分别去第一个数的index i和第二个数的index j， index j之后用 hashm ...

感觉还是排序好一些