java - 将数组中的每个元素与其他元素相加的有效解决方案

Question

这看起来很微不足道，不是家庭作业问题。

public void sum(int[] arr){
  for(int i=0;i<arr.length;i++)
  {
    for(int j=0;j<arr.length;j++)
      System.out.println(arr[i]+"+"+arr[j]+"+"+"="+(arr[i]+arr[j]));
  }   
}//end of sum function

这会打印每个元素的所有总和。这是 O(n^2)。

我想知道是否可以更有效地解决这个问题。

Answer 1

由于 A + B 等于 B + A，因此您可以只检查索引 i 中初始元素之后的元素:

public void sum(int[] arr){
  for(int i=0;i<arr.length;i++)
  {
    for(int j=i;j<arr.length;j++) //Note: j = i, not j = 0
      System.out.println(arr[i]+"+"+arr[j]+"+"+"="+(arr[i]+arr[j]));
  }   
}//end of sum function

它仍然是 O(n^2)/2，因此复杂度仍然基本上是二次的。