搜索
您的当前位置:首页正文

和为0的最长子串

来源:欧得旅游网

已知一个数组只有 1和-1,求它和为0的最长子串长度。如 数组{-1,1,-1,-1,1,1,1,1,1} 和为0的最长子串为 {-1,1,-1,-1,1,1} 答案为6.

之前一直想的是用动态规划,但是试了半天一直没有找到规律,后来看了看这篇文章: 顿时有了思路,下面是我实现的代码:

#include<iostream>
#include<map>
using namespace std;
int getLen(int *array,int length){
    map<int,int> cmap;
    int result =0,sum =0;
    cmap[0]=-1;
    for(int i =0;i<length;i++){
        sum+=array[i];
        if(cmap.find(sum)==cmap.end()){
            cmap[sum]=i;
        }else if(i-cmap[sum] >result) result = i-cmap[sum];
    }
    return result;
}
int main(){
    int nums[]={-1,1,1,1,1,-1,-1,-1};
    cout<<getLen(nums,8);
    return 0;
}


因篇幅问题不能全部显示,请点此查看更多更全内容

Top