返回無序數組中正數和負數個數相等的最長子數組長度

思路

跟未排序數組中累加合為定值的最長子數組長度很像，只是現在要判斷符號，把所有數值都分類為 $0, -1, 1$ 三種數值。
配對的target此時就是數字 $0$，所以在哈希表找的目標是當前的sum。

程式碼

前綴和

#include <iostream>
#include <unordered_map>
#include <climits>
using namespace std;

int main() {
    int n;
    cin >> n;
    int res = 0;
    unordered_map<int, int> umap;
    umap[0] = -1;
    int x; 
    int sum = 0;
    for(int i = 0; i < n; ++i) {
        cin >> x;
        if(x > 0) sum++;
        else if(x < 0) sum--;
        if(umap.find(sum) != umap.end()) { // 同樣的前綴和, 代表中間這段長度的總合為 0
            res = max(res, i - umap[sum]);
        }
        else { // 第一次出現
            umap[sum] = i;
        }
    }
    cout << res;
}

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$