Judge:https://vjudge.net/problem/UVA-11572
题意:在一个长度最多为10^6的序列中找到一个尽量长的、没有相同元素的连续子序列。
贪心,滑动窗口问题。把左端点、右端点放在最左边,然后把右端点尽量往右延伸,当无法延伸的时候,增大L,再重复上面的操作。
有人使用了set判断能否延伸,但我听说set的时间复杂度虽然是O(logn),但它的常数有点大。
实际上哈希就行。
#include <iostream> #include <cstring> #include <algorithm> using namespace std; struct SHashNode { long long iData; SHashNode * pNext; }; long long g_arrNum[1000010]; SHashNode g_arrHash[23456789]; SHashNode * CreateHashNode(long long iData = 0, SHashNode * pNext = 0) { SHashNode * pTmp = new SHashNode; pTmp->iData = iData; pTmp->pNext = pNext; return pTmp; } bool InsertHash(long long iData) { int i = iData % 23456789; if (i < 0) i += 23456789; SHashNode * pNode = &g_arrHash[i]; while (pNode->pNext) { if (pNode->pNext->iData == iData) return false; pNode = pNode->pNext; } pNode->pNext = CreateHashNode(iData); return true; } bool DeleteHash(long long iData) { int i = iData % 23456789; if (i < 0) i += 23456789; SHashNode * pNode = &g_arrHash[i]; while (pNode->pNext) { if (pNode->pNext->iData == iData) { pNode->pNext = pNode->pNext->pNext; return true; } pNode = pNode->pNext; } return false; } int main() { int iDataTot; cin >> iDataTot; while (iDataTot--) { memset(g_arrNum, 0, sizeof(g_arrNum)); memset(g_arrHash, 0, sizeof(g_arrHash)); int iNumTot; cin >> iNumTot; for (int i = 1; i <= iNumTot; i++) cin >> g_arrNum[i]; int iLeft = 1, iRight = 1, iResult = 0; while (iRight <= iNumTot) { while (iRight <= iNumTot && InsertHash(g_arrNum[iRight])) { iResult = max(iResult, iRight - iLeft + 1); iRight++; } DeleteHash(g_arrNum[iLeft]); iLeft++; iResult = max(iResult, iRight - iLeft + 1); } cout << iResult << endl; } return 0; }