和为0的最长连续子数组【转载+优化代码】

 1 #include <cstdio>
 2 #include <map>
 3 #include <vector>
 4 #include <iostream>
 5 #include <cstdlib>
 6 
 7 using namespace std;
 8 
 9 int main()
10 {
11     int n,val;
12     while (cin >> n) {
13         vector<int> arr(n + 1);
14         for (int i = 1; i <= n; i++) {
15             cin >> val;
16             arr[i] = val;
17         }
18         vector<int> dp(n + 1);
19         dp[1] = arr[1];
20         for (int i = 2; i <= n; i++)
21             dp[i] = arr[i] + dp[i - 1];
22 
23         //求取dp[i] = dp[j],i表示dp[i]的值第一次出现的位置，j表示其最后一次出现的位置
24         //for (const auto &s : dp)
25         //    cout << s << " ";
26         //cout << endl;
27         map<int, int> m;
28         int begin, max = 0;
29         for (int i = 1; i <= n; i++) {
30             begin = m[dp[i]];
31             if (begin == 0 && dp[i] != 0) {
32                 m[dp[i]] = i;
33             }
34             else {
35                 if (i - begin > max) {
36                     max = i - begin;
37                 }
38             }
39         }
40         cout << max << endl;
41     }
42     return 0;
43 }

 1 #include <iostream>
 2 #include <vector>
 3 #include <map>
 4 using namespace std;
 5 
 6 int main(){
 7     int n;
 8     while(cin>>n){
 9         vector<int> v(n);
10         for(int i=0;i<n;++i){
11             cin>>v[i];
12         }
13         vector<int> dp(n);
14         dp[0]=v[0];
15         for(int i=1;i<n;++i){
16             dp[i]=dp[i-1]+v[i];//计算前缀和
17         }
18 
19         int result=0;
20         map<int,int> m;
21         for(int i=0;i<n;++i){
22             if(0!=dp[i])//0就不插入了，直接计算和开始位置之间的距离（也就是减去-1）
23                 m.insert(pair<int,int>(dp[i],i));
24             int val= (0==dp[i])?(i+1):(i-m[dp[i]]);
25             result=max(result,val);
26         }
27         cout<<result<<endl;
28     }
29     return 0;
30 }