java - 三和问题的以下算法的复杂性

Question

给定 n 个整数的排序列表 (a[0],...,a[n-1])。我需要找到三个不同的 索引 p、q、r，使得三元组 (a[p]、a[q]、a[r]) 满足方程 a[p]+a[q ]+a[r]=0。此外，排序列表可以多次包含相同的数字。所需的算法必须是二次的。

我找到了一个解决方案(我绝对不是说它是最有效的解决方案)，但我很确定它不是二次方的(2 个 for 循环和一个 while 循环)。这是我的代码:

public ThreeSumIndices searchTriplet(List<Integer> list) {
    for(int i=0; i<list.size()-1; i++){
        int w = -list.get(i);
        for(int j=i+1; j<list.size(); j++){
            int k = 1;
            while(j+k<list.size() && list.get(j)+list.get(j+k)!=w){
                k++;
            }
            if(j+k==list.size()){
                k = 1;
            } else if(list.get(j)+list.get(j+k)==w){
                return new ThreeSumIndices(i,j,j+k);
            }
        }
    }
    return null; //no indices found.
}

ThreeSumIndices 是一个单独的类。它以 (p,q,r) 的形式返回我们要查找的索引。构造函数参数是三个整数(=三个索引)。

示例:(-5, 1, 2, 3, 7) --> (0,2,3)。

我对复杂性分析还很陌生，所以我想知道我对这个算法不是二次方的猜测是否正确。

如果是这样，有没有办法摆脱循环？或者可能有其他更有效的算法？

谢谢。

Answer 1

如果数组已排序，那么您需要做的就是:

• 运行从 i=0 到 n-2 的循环。
• 初始化两个索引变量l=i+1和r=n-1
• while:l
• 如果sum小于零，则自增l(l++)，否则自减r(r--)

• 扫描所有元素。

  for (int i=0; i < n-1; i++) {
      int l = i + 1; 
      int r = n - 1; 
      int x = arr[i]; 
      while (l < r){ 
          if (x + arr[l] + arr[r] == 0) print()
          else if(x + arr[l] + arr[r] < 0) l++;
          else r--; 
      } 
  }
  

这段代码的时间复杂度为 O(n^2)，空间复杂度为 O(1)