一种被称作滑动窗口的算法

shao 发表于 4年前 · 关联问题 一鸣师姐的投资计划

此算法空间复杂度较高,寻找最长不重复子串,核心代码(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; }

shao 发表于 4年前

本来是用vector的,但是vector太慢了(笑哭

shao 发表于 4年前

纠正个错字:sliding

我好鶸 发表于 2年前

看到了这个分享我才知道有"滑动窗口算法" 感谢大爹!!(AC辽