正数与负数个数相等的最长子数组

未排序数组中累加和为给定值的最长子数组系列问题补1

题目描述：

给定一个无序数组arr，其中元素可正、可负、可0。求arr所有子数组中正数与负数个数相等的最长子数组的长度。

[要求]

时间复杂度为 O ( n ) O(n) O(n)，空间复杂度为 O ( n ) O(n) O(n)

输入描述：

第一行一个整数N，表示数组长度
接下来一行有N个数表示数组中的数

输出描述：

输出一个整数表示答案

示例1

输入

5
1 -2 1 1 1

输出

2

备注：

1 ≤ N ≤ 1 0 5 1 \leq N \leq 10^5 1≤N≤105
− 100 ≤ a r r i ≤ 100 -100 \leq arr_i \leq 100 −100≤arri​≤100

---

题解：

前缀和，把负数当作 -1 ，正数当作 1，然后就是求和为0的最大子数组长度，这不又回到了 未排序数组中累加和为给定值的最长子数组长度 这题上面嘛，一题是求和为 K ，一题是求和为 0 ，解法一样。

代码：

#include <cstdio>
#include <unordered_map>

using namespace std;

unordered_map<int, int> _hash;

int n, val;

int main(void) {
    scanf("%d", &n);
    int sum = 0;
    _hash[0] = -1;
    int ret = 0;
    for ( int i = 0; i < n; ++i ) {
        scanf("%d", &val);
        if ( val < 0 ) sum += -1;
        else if ( val > 0 ) sum += 1;
        if ( _hash.find( sum ) != _hash.end() ) ret = max( ret, i - _hash[sum] );
        else _hash[sum] = i;
    }
    return 0 * printf("%d\n", ret);
}