Amazon : Find first pair sum to zero

given an array with positive and negative numbers find the first continuous subarray that sums to 0

最近碰到的都是水点的题，对不住了...

比如a[0..i]的sum == a[0..j]的sum
那么a[i+1..j]这个subarray的sum就为0，
用hash表记录sum(a[0]),sum(a[0]+a[1]),...sum(a[0]+...+a[i])的值
O(n)时间复杂度，O(N)空间复杂度

bool FindFirstPair(int& nStart, int& nEnd, int a[], int n)
{
        nStart = nEnd = n;
        int nCount = 0;
        hash_map<int, int> hash;
        bool bSet = false;
        for (int i = 0; i < n; i++)
        {
                nCount += a[i];
                if (0 == nCount)
                {
                        nStart = 0;
                        nEnd = i;
                        return true;
                }

                if (hash.find(nCount) == hash.end())
                        hash[nCount] = i;
                else
                {
                        int nIndex = hash[nCount];
                        if (nIndex+1 < nStart || (nIndex+1 == nStart && i - nIndex - 1 < nEnd - nStart))
                        {
                                nStart = nIndex+1;
                                nEnd = i;
                                bSet = true;
                        }
                }
        }

        return bSet;
}

vector<int> findSubArray(const vector<int>& v)
{
        vector<int>::const_iterator i;
        map<int, vector<int>::const_iterator > count;
        int sum = 0;
        for (i = v.begin(); i != v.end(); ++i)
        {
                sum += *i;
                if(0 == sum)
                        return vector<int>(v.begin(), i + 1);
                if(count.find(sum) == count.end())
                        count[sum] = i;
                else
                        return vector<int>(count[sum] + 1, i + 1);
        }
        return vector<int>();
}
思路差不多

版主啊 我知道你的妹纸头像很拉轰 但是我真的晃得眼睛都花了 换个静态的吧 拜谢