学步园

今天在CareerCup 看到一个Amazon的面试题：

Given 2 binary arrays A and B i.e. containing only 0s and 1s each of size N. 
Find indices i,j such that Sum of elements from i to j in both arrays is equal and j-i (i.e. the length of the set i,j) is the maximum
possible value.

链接：http://www.careercup.com/question?id=25036663

O(n2)的算法看到很好想啦，当时也想到建立两个前缀和，然后用window滑动来寻找合适的区间，但是想了下当 （i,j)的时候，怎么来决定下一步是(i+1,j) ，和(i,j-1)，然后好像没有比较好的想法。

后来看到下面一个匿名留言：

This is same as finding the longest subarray with sum zero in the
array C[i] = A[i] - B[i]. 

Prefix sums + hashtable should give it.

豁然开朗：

具体思路我在那下边有留言了，拷过来：

This algo works ! And it's indeed
O(n) .
Say we have two Arrays: 
A=[ 0 1 0 0 0 1 0 0 1 0 0] 
B=[ 1 0 1 1 1 0 1 1 0 1 0] 
Then we create two arrays : C[i] = A[i] - B[i] . D[i] = D[i-1] + C[i];
C=[-1 1 -1 -1 -1 1 -1 -1 1 -1 0] 
D=[-1,0,-1,-2,-3,-2,-3,-4,-3,-4,-4]
now we consider D-array. if D[i] == D[j] , what does it means ?
it means sum( C[i,j ] ) ==0 . 
and since C[i] =A[i] - B[i] , now it means sum( A[i,j] ) == sum ( B[i, j] )
so now the task becomes find two indices in D[] ,and (j - i) is maximum.
we need the help of HashMap.
Here is the algo:
1.create D[] Array. init a empty hash_map
2.traverse the D[] Array , if D[j] exists in hash_map (let's say its valus is i ),then we update the answer with (i, j ) ;
3. if D[j] doesn't exist in hash_map , insert it !
4.finally ,we got the answer , and now you see we only traverse the D[] array one time , so the complexity is O(n ).
5. thanks!

然后上代码：

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cassert>
using namespace std;

int findMaxIndices(const vector<int>& a,const vector<int>& b)
{
	int na = a.size(),nb =b.size();
	assert(na==nb);
	vector<int> c(na,0);
	for(int i=0;i<na;i++)
		c[i]=a[i]-b[i];
	for(int i=1;i<na;i++)
		c[i]=c[i-1]+c[i];

	int ret=-1;

	map<int,int> exist;
	map<int,int>::iterator it;
	exist.insert(pair<int,int>(0,-1));
	for(int i=0;i<na;i++)
	{
		it = exist.find(c[i]);	
		if ( it==exist.end() )
			exist.insert(it,pair<int,int>(c[i],i));
		else
		{
			ret=max(ret, (i-it->second) );
		}
	}
	return ret;
}

int main()
{
	int n;
	while(cin>>n)
	{
		if ( n==0 )
			break;
		vector<int> a(n,0);
		vector<int> b(n,0);
		for(int i=0;i<n;i++)
			cin>>a[i];
		for(int i=0;i<n;i++)
			cin>>b[i];

		int ret= findMaxIndices(a,b);
		cout << ret <<endl;
	}
}