这有可能在O（n）时间内生成子阵列吗？

Question

我试图在下面的代码的帮助下生成子阵列，但是这个代码的时间复杂度在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;
}

Answer 1

如果您不需要列表独立于原始列表a，您可以使用List的subList方法。 https://docs.oracle.com/javase/7/docs/api/java/util/List.html

这将降低O(n^2)的复杂性。