forked from hongtaocai/code_interview
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path4sum.java
More file actions
executable file
·91 lines (81 loc) · 2.68 KB
/
4sum.java
File metadata and controls
executable file
·91 lines (81 loc) · 2.68 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/**
*/
package com.leetcode;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
public class Solution {
class TwoSum{
public int index1,index2,sum;
public TwoSum(int index1, int index2, int sum){
this.index1 = index1;
this.index2 = index2;
this.sum = sum;
}
}
ArrayList<TwoSum> ts = new ArrayList<TwoSum>();
public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
// Start typing your Java solution below
// DO NOT write main() function
ts.clear();
HashSet<ArrayList<Integer>> s = new HashSet<ArrayList<Integer>>();
ArrayList<Integer> tmp = new ArrayList<Integer>();
for(int i=0;i<num.length-1;i++){
for(int j=i+1;j<num.length;j++){
ts.add(new TwoSum(i,j,num[i]+num[j]));
}
}
Collections.sort(ts,new Comparator<TwoSum>() {
@Override
public int compare(TwoSum twoSum, TwoSum twoSum1) {
return twoSum.sum-twoSum1.sum;
}
});
int i=0;
int j=ts.size()-1;
while(i<j){
if(ts.get(i).sum+ts.get(j).sum<target){
i++;
}
else if(ts.get(i).sum+ts.get(j).sum>target){
j--;
}else{
tmp.clear();
tmp.add(ts.get(i).index1);
tmp.add(ts.get(i).index2);
tmp.add(ts.get(j).index1);
tmp.add(ts.get(j).index2);
Collections.sort(tmp);
if(tmp.get(0).equals(tmp.get(1))
|| tmp.get(1).equals(tmp.get(2))
|| tmp.get(2).equals(tmp.get(3)) )
{
}
else{
ArrayList<Integer> tmparr = new ArrayList<Integer>();
tmparr.add(num[tmp.get(0)]);
tmparr.add(num[tmp.get(1)]);
tmparr.add(num[tmp.get(2)]);
tmparr.add(num[tmp.get(3)]);
Collections.sort(tmparr);
s.add(tmparr);
}
if(ts.get(i).sum == ts.get(i+1).sum && i+1<j){
i++;
}
else if(ts.get(j).sum == ts.get(j-1).sum && i+1<j){
j--;
}else{
i++;
j--;
}
}
}
return new ArrayList<ArrayList<Integer>>(s);
}
public static void main(String args[]){
int[] kkk = {};
System.out.println(new Solution().fourSum(kkk, 0).size());
}
}