我试图借助以下代码生成子数组,但该代码的时间复杂度为 O(n^3)。请帮我找出最佳的方法。
我的代码如下:
static ArrayList<ArrayList<Integer>> solve(List<Integer> a) {
ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
for(int i=0;i<a.size();i++)
{
for(int j=i;j<a.size();j++)
{
ArrayList<Integer> temp=new ArrayList<Integer>();
for(int k=i+1;k<=j;k++)
{
temp.add(a.get(k));
}
res.add(temp)
}
}
return res;
}
最佳答案
如果您不需要列表独立于原始列表a
,您可以使用List
的subList
方法。
https://docs.oracle.com/javase/7/docs/api/java/util/List.html
这会将复杂度降低至 O(n^2)
。
关于java - 是否可以在 O(n) 时间内生成子数组?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52234455/