未排序數組中累加合為定值的最長子數組長度

推薦事前閱讀：前綴和介紹

思路

給定一個數組 $[10,0,-20,20,-20]$ ，target = 0，求元素總和為target的最長子數組。
如果單純用前綴數組，需要 $O(n^2)$ 的複雜度去找到所有子數組的總和，依舊太慢，需要優化。

範例的前綴數組是 $[\orange0,10,10,-10,10,-10]$ ，
對於第一個 $-10$ 來說，前面需要 $10$ 跟它配對成目標數字 $0$ ，
而在它前面有兩個 $10$ 。第一個對應到的子數組比較長，所以選它。
對第二個 $-10$ 來說，同樣只需要考慮第一個 $10$ ，因為它最前面。
可以利用這個特性去優化計算。

使用哈希表去優化計算過程，當前綴出現第一次的時候，就將它的位置記錄下來，
假如後面有能配對的，就將當前位置跟哈希表中紀錄的位置相減。

程式碼

前綴和

#include <iostream>
#include <array>
#include <unordered_map>
using namespace std;
int main() {
    int res = 0;
    int n, target;
    cin >> n >> target;
    unordered_map<int, int> umap; // 紀錄該前綴最早出現的位置
    umap[0] = -1; // 數字 0 要跟 0 配，假如第一個位置是 0, 答案是 0 - (-1) = 1
    int sum = 0, num;
    for(int i = 0; i < n; i++) {
        cin >> num;
        sum += num;
        if(umap.find(sum - target) != umap.end()) { // 跟自己配對的數字有出現過
            res = max(res, i - umap[sum - target]); // 更新答案
        }
        if(umap.find(sum) == umap.end()) { // 第一次出現的數字, 計入 umap
            umap[sum] = i;
        }
    }
    cout << res;
}

複雜度分析

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