OJ 比赛列表有蓝桥杯、CCF-CSP、天梯赛官方练习系统 / 题目集入口,有需要测试比赛评测环境的可以前往。

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

王家晔(HK-SHAO) 发表于 5个月前 · 关联问题 一鸣师姐的投资计划

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

王家晔(HK-SHAO) 发表于 5个月前

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

王家晔(HK-SHAO) 发表于 5个月前

纠正个错字:sliding