查找连续的子数组（无总和）

Question

我想询问为给定数组查找连续子数组的快速方法。请注意，我不是在寻找最大和连续子数组，而是想对获得的子数组执行其他操作。我已经知道以下算法，但正在寻找更有效的算法，因为这个算法的时间复杂度很低。

// N = number of elements in array A.
void subarr(int N, int A[]) {
  for (int i = 0; i < N; i++) {
    for (int j = i; j < N; j++) {
      for (int k = j; k < N; k++) {
        cout << A[k] << ' ';
      }
      cout << endl;
    }
  }
}

Answer 1

正如其他人在评论中指出的那样，您的示例不正确。它应该读作

for (int i = 0; i < N; i++) {
   for (int j = N-1; j >= i; j--) {
      for (int k=i; k<=j; k++) {
         cout << "A[" << k << "] ";
     }
     cout << endl;
   }
}

请注意，我将输出更改为直接打印 A[k]。这将只打印每个子数组一次。

关于你的问题，正如其他人所指出的，该算法只打印一次每个子数组，没有任何额外的工作。我不相信你可以节省运行时间，因为这几乎是你必须做的最少工作量。三个嵌套循环确实有一些开销，但您可能需要所有三个：子数组由例如

指定

它的起点
它的终点或它的长度

你必须print/cut找出中间的内容，从而产生第三个循环。

查找连续的子数组（无总和）

Finding contiguous subarray (without sum)

c++

sub-array