994. 连续数组

    xiaoxiao2023-11-27  185

    题目链接:

    https://www.lintcode.com/problem/contiguous-array/description

    给一个二进制数组,找到 0 和 1 数量相等的子数组的最大长度

    Example

    样例 1:

    输入: [0,1] 输出: 2 解释: [0, 1] 是具有相等数量的 0 和 1 的最长子数组。

    样例 2:

    输入: [0,1,0] 输出: 2 解释: [0, 1] (或者 [1, 0]) 是具有相等数量 0 和 1 的最长子数组。

    Notice

    给出的二进制数组的长度不会超过 50,000。

    思路1:双重循环

    思路2:1)将0看作是-1, 如1,0,0,0,1,1,0 看作 1,-1,-1,-1,1,1,-1.

                 2) 假定max记录最长子数组的长度,循环求数组的和sum。 

                     若此时的sum在之前未出现过,则加入hashMap,记录sum和对应下标i;

                     若此时的sum在之前出现过,说明之前某个下标j到当前下标i的和为0,说明0和1出现的次数相同,记录j-i并与max比较

    最新回复(0)