java - 为什么数组比ArrayList快得多？

最近，我尝试解决Problem 23 of Project Euler。为此，我首先创建一个包含所有丰富数字的列表，称为abundants。

接下来，我遍历此列表，并构建另一个列表，该列表包含所有低于一定限制的大量数字。现在我注意到了一些奇怪的事情。我使用嵌套循环在列表上进行两次迭代。但是，如果我使用数组存储和，则需要花费几秒钟，如果将和添加到ArrayList中，则需要花费数小时。是什么原因呢？我以为昂贵的操作是两个嵌套循环，但似乎昂贵的操作是ArrayList＃add。有什么暗示为什么会这样吗？

这是数组的代码:

for (int i = 0; i < abundants.size(); i++) {
   for (int j = 0; j < abundants.size(); j++) {
      int tot = abundants.get(i) + abundants.get(j);
      if (tot <= limit)
         isSum[tot] = true;
      }
   }
}

这里是ArrayList的代码:

ArrayList<Integer> sums = new ArrayList<Integer>();
for (int i = 0; i < abundants.size(); i++) {
   for (int j = 0; j < abundants.size(); j++) {
      int s = abundants.get(i) + abundants.get(j);
      if (!sums.contains(s) && s < limit) {
         sums.add(s);
      }
   }
 }

最佳答案

您的ArrayList实现是O(n ^ 3)，而另一个是O(n ^ 2):对于您的内部循环的每次迭代，sums.contains(...)必须遍历整个sums列表。