s*****9
发帖数: 93 | 1 用了DP，同时用了HashSet防止重复结果，运行时间无法通过Large Test. HashSet的查
找不是应该O(1)时间吗？怎样才能更快呢？请帮忙看一下：
import java.util.*;
public class Solution {
public ArrayList> threeSum(int[] num) {
HashSet> final_set = new HashSet
Integer>>();
ArrayList current_list = new ArrayList();
threeSumRecur(num, 0, current_list, final_set);
ArrayList> final_lists = new ArrayList
Integer>>();
for(ArrayList element : final_set) {
final_lists.add(element);
}
return final_lists;
}
public void threeSumRecur(int[] num, int index, ArrayList
current_list, HashSet> final_set) {
if(index >= num.length) {
return;
}
current_list.add(num[index]);
if(current_list.size() >= 3) {
if(current_list.get(0) + current_list.get(1) + current_list.get(
2) == 0) {
ArrayList new_list = new ArrayList();
new_list.addAll(current_list);
Collections.sort(new_list);
if(!final_set.contains(new_list)) {
final_set.add(new_list);
}
}
}
else {
threeSumRecur(num, index + 1, current_list, final_set);
}
current_list.remove(current_list.size() - 1);
threeSumRecur(num, index + 1, current_list, final_set);
}
} | Z*****Z
发帖数: 723 | 2 你这是O（N3）的算法
ArrayList<
【在 s*****9 的大作中提到】
: 用了DP，同时用了HashSet防止重复结果，运行时间无法通过Large Test. HashSet的查
: 找不是应该O(1)时间吗？怎样才能更快呢？请帮忙看一下：
: import java.util.*;
: public class Solution {
: public ArrayList> threeSum(int[] num) {
: HashSet> final_set = new HashSet: Integer>>();
: ArrayList current_list = new ArrayList();
: threeSumRecur(num, 0, current_list, final_set);
:
| s*****9
发帖数: 93 | 3 多谢点拨!我根本就没使用DP，纯递归啊!
【在 Z*****Z 的大作中提到】
: 你这是O（N3）的算法
:
: ArrayList<
|
|
