前几天猿题库的笔试题，想了挺久不知道咋做，中午问了慧伟，刚给出了答案。一直以为用动态规划，其实不然。

题目是这样的：一个一维数组中只有1和-1，实现程序，求和为0的最长子串长度，并在注释中给出时间和空间复杂度。

思路就是在i从0到n，计算sum(i)，sum(i)表示从0到i的元素之和。并保存在字典dic中，value是索引i，在往后的遍历中每得到一个sum(i)就查看dic的keys是否已有此sum(i)值，如果有则用当前i位置减去保存的i，并与maxLen比较，取大的那个。遍历结束，给出结果。时间复杂度O(n)，空间复杂度O(1)。

Python代码：

# coidng:utf-8
# @sinner
# 16/9/8

class Solution(object):
    def fun(self, l):
        dic = {0:-1}
        sum = 0
        maxLen = 0
        for x in xrange(0, len(l)):
            sum += l[x]
            if sum in dic: maxLen = max(maxLen, x - dic[sum])
            else: dic[sum] = x
        return maxLen


print Solution().fun([1, -1, -1, -1, 1, 1, 1, -1, -1])

输出为8.