Longest Subarray Of Sum Is Zero

问题描述：

一个长度为N的数组中，包含正数、负数、零。请实现一个函数找出最长的和为零的连续子数组。

输入：

所有数组元素在一行，元素之间以空格分割。

输出：

所有数组元素在一行，元素之间以空格分割。

例如：

输入： 7 -7 8 6 5 -5 -5 0 -6 11

输出： 5 -5 -5 0 -6 11

题目和思路

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

pair<int, int> longestSubarrayOfSumIsZero(vector<int> &arr){
    pair<int, int> res = make_pair(-1, -1);
    int n = arr.size();
    if(n <= 0)  return {};

    //key = sum[i], value = i
    unordered_map<int, int> hashmap;
    vector<int> sum(n, 0);
    sum[0] = arr[0];

    int maxLen = 0;
    for(int i = 1; i < n; i++){
        sum[i] = sum[i - 1] + arr[i];
        if(hashmap.find(sum[i]) != hashmap.end()){
            int len = i - hashmap[ sum[i] ];
            if(len > maxLen){
                res.first = hashmap[sum[i]] + 1;
                res.second = i;
            }
        }else{
            hashmap[sum[i]] = i;
        }

        if(sum[i] == 0){
            if(i > maxLen){
                res.first = 0;
                res.second = i;
            }
        }

    }
    return res;
}


int main(){
//vector<int> test = {7, -7, 8, 6, 5, -5, -5, 0, -6, 11,-14};
    vector<int> test = {1,2 , 3, 4, 5, 6};
    auto ret = longestSubarrayOfSumIsZero(test);

    int st = ret.first;
    int en = ret.second;

    if(st != en){
        cout<<"start from:"<<st<<" "<<"end at:"<<en<<endl;
        for(int i = st; i <= en; i++)
            cout<<test[i]<<" ";
    }else{
        cout<<"No subarray's sum equal 0";
    }
    cout<<endl;

    return 0;
}