agou.win
BAN USERUse cumulative array for comparing...
int maxCommonArray(int A[], int B[], int n)
{
unordered_map<int, vector<int>> dist;
int ASum = 0, BSum = 0, ABDiff;
for (int i=0; i<n; i++)
{
ASum = ASum+A[i];
BSum = BSum+B[i];
ABDiff = ASum-BSum;
dist[ABDiff].push_back(i);
}
//Get the max length;
int maxLength = -1;
unordered_map<int, vector<int>>::iterator dI;
for (dI = dist.begin(); dI != dist.end(); dI++)
{
vector<int> crt = dI->second;
int sizeC = crt.size();
int crtLen = crt[sizeC-1] - crt[0];
if (crtLen>maxLength)
maxLength = crtLen;
}
return maxLength;
}
This is O(n^2)... It can be O(n)
- agou.win August 10, 2013