此算法空间复杂度较高,寻找最长不重复子串,核心代码(s是序列,v是s的缓存)
int len = m, ans = 0, start = -1;
for (int j = 0; j < len; j++)
{
if (v[s[j]] > start) // Slding Window
start = v[s[j]];
v[s[j]] = j;
ans = max(ans, j - start);
}
AC代码
#include <bits/stdc++.h>
using namespace std;
int v[2010];
int aa[2010];
int s[2010];
int main(void)
{
int n, m, anss = 0;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
scanf("%d", &s[j]);
memset(v, -1, sizeof(v));
int len = m, ans = 0, start = -1;
for (int j = 0; j < len; j++)
{
if (v[s[j]] > start) // Slding Window
start = v[s[j]];
v[s[j]] = j;
ans = max(ans, j - start);
}
aa[i] = ans;
anss = max(anss, aa[i]);
}
cout << anss << endl;
for (int i = 0; i < n; i++)
if (aa[i] == anss)
cout << i + 1 << ' ';
return 0;
}
本来是用vector的,但是vector太慢了(笑哭
纠正个错字:sliding
看到了这个分享我才知道有"滑动窗口算法" 感谢大爹!!(AC辽