Возможно ли создать подмассив за 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).