以小于 O(n^3) 的时间复杂度打印所有子数组

Question

要打印给定数组的所有子数组（连续子序列），需要三个嵌套的 for 循环。有没有办法在C++ STL中使用map来降低O(n^3)的时间复杂度？

#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio (false);
cin.tie(NULL);
cout.tie(NULL);
vector<int> v;
int n;
cin>>n;   // the size of the array
for(int i=0;i<n;i++)
{
int x;
cin>>x;
v.push_back(x);
}
for(int i=0;i<n;i++)
{
for(int j=i;j<n;j++)
{
for(int k=i;k<=j;k++)
cout<<v[k]<<" ";
cout<<endl;
}
}
return 0;
}

Answer 1

如果您必须迭代所有元素，那么您必须迭代所有元素...不可能进一步减少。降低时间复杂度就是找到不需要迭代所有元素的方法。