4sum o(n^2)超时# JobHunting - 待字闺中
m*1
1 楼
写了一个平方复杂度的，但是一直超时。请大家帮忙看看。
public ArrayList> fourSum(int[] num, int target) {
Map cache = new HashMap();
Map> previous = new HashMap
ArrayList> result = new ArrayList
Set nima = new HashSet();
if (num.length < 4) {
return result;
}
Arrays.sort(num);
for (int i = 0; i < num.length; i++) {
for (int j = i+1; j < num.length; j++) {
List lastTwo = new ArrayList();
lastTwo.add(num[i]);
lastTwo.add(num[j]);
previous.put(i+"+"+j, lastTwo);
cache.put(i+"+"+j, num[i]+num[j]);
}
}
for (String start : cache.keySet()) {
int c = target-cache.get(start);
String[] numbers = start.split("\+");
int left = Integer.valueOf(numbers[1])+1;
int right = num.length-1;
while (left < right) {
int sum = num[left] + num[right];
if (sum < c) {
left++;
} else if (sum > c) {
right--;
} else {
List lastTwo = previous.get(start);
String key = start+"+" +left+ "+"+right;
if (!nima.contains(key)) {
ArrayList list = new ArrayList();
list.addAll(lastTwo);
list.add(num[left]);
list.add(num[right]);
result.add(list);
nima.add(key);
}
right--;
left++;
}
}
}
return result;
}
public ArrayList
Map
Map
ArrayList
Set
if (num.length < 4) {
return result;
}
Arrays.sort(num);
for (int i = 0; i < num.length; i++) {
for (int j = i+1; j < num.length; j++) {
List
lastTwo.add(num[i]);
lastTwo.add(num[j]);
previous.put(i+"+"+j, lastTwo);
cache.put(i+"+"+j, num[i]+num[j]);
}
}
for (String start : cache.keySet()) {
int c = target-cache.get(start);
String[] numbers = start.split("\+");
int left = Integer.valueOf(numbers[1])+1;
int right = num.length-1;
while (left < right) {
int sum = num[left] + num[right];
if (sum < c) {
left++;
} else if (sum > c) {
right--;
} else {
List
String key = start+"+" +left+ "+"+right;
if (!nima.contains(key)) {
ArrayList
list.addAll(lastTwo);
list.add(num[left]);
list.add(num[right]);
result.add(list);
nima.add(key);
}
right--;
left++;
}
}
}
return result;
}
