arrays - 以 O(n) 复杂度查找数组的所有连续子数组

Question

我一直在寻找一种解决方案，以最小时间复杂度 O(n) 查找给定数组的所有连续子数组。

例如:

[1,2,3,4] 

子数组是:

[1][2][3][4][1,2][2,3][3,4][1,2,3][2,3,4][1,2,3,4]

我已经以时间复杂度 O(n^2) 完成了它，但是对于大输入来说需要大量的时间和内存。

这个问题有没有具体的算法？

Answer 1

正好有 n(n+1)/2 个子数组，对于所有 i 且所有 j≥i，可以将其写为 A[i..j]。生成所有对的算法是立即的(双循环)并且无法改进。

如果您只需要输出 (i, j) 对，空间 O(1) 就足够了。如果您需要存储所有对，则 O(n²)。如果您需要完整存储所有子数组，则 O(n³)；在这种情况下，时间也不可避免地增长到 O(n3)，并且存在另一个嵌套循环。

---

更新:

这个答案没有考虑注释中的约束“这些单独子数组的总和得到完美的平方根”，这是事后添加的，不能被视为问题的一部分。