CodeForces - 873B - Balanced Substring 【前缀和+map】题解

分手后的思念是犯贱 2021-08-30 01:01 286阅读 0赞

### 1.题目 ###

You are given a string s consisting only of characters 0 and 1. A substring \[l, r\] of s is a string s l s l + 1 s l + 2… s r, and its length equals to r - l + 1. A substring is called balanced if the number of zeroes (0) equals to the number of ones in this substring.

You have to determine the length of the longest balanced substring of s.

**Input**  
The first line contains n (1 ≤ n ≤ 100000) — the number of characters in s.

The second line contains a string s consisting of exactly n characters. Only characters 0 and 1 can appear in s.

**Output**  
If there is no non-empty balanced substring in s, print 0. Otherwise, print the length of the longest balanced substring.

Examples  
**Input**  
8  
11010111  
Output  
4  
**Input**  
3  
111  
**Output**  
0  
**Note**  
In the first example you can choose the substring \[3, 6\]. It is balanced, and its length is 4. Choosing the substring \[2, 5\] is also possible.  
In the second example it’s impossible to find a non-empty balanced substring.

### 2.代码 ###

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<string>
    #include<map>
    using namespace std;
    const int maxn = 1e5 + 10;
    int a[maxn];
    map<int, int>mp;
    int main()
    { 
    	int n;
    	string str;
    	cin >> n>>str;
    	for (int i = 1; i <=n; i++)//将字符串转换为int数组
    	{ 
    		a[i]=str[i-1]-'0';
    		if (a[i] == 0)
    		{ 
    			a[i] = -1;
    		}
    	}
    	int ans=0,sum=0;
    	for (int i = 1; i <=n; i++)
    	{ 
    		sum += a[i];  //前缀和
    		if (mp[sum])
    		{ 
    			ans = max(ans, i - mp[sum]);//如果之前存在过这个和，现在又出现了，说明这个区间1，0个数是相同的，相减为长度
    		}
    		else
    		{ 	
    			mp[sum] = i;//利用map不能重复插入的特性，所以如果存在一定是这个值第一次出现时的位置
    		}
    		if (sum == 0)//如果前缀和出现零说明从一开始就是1,0个数相同
    		{ 
    			ans = max(ans, i);
    		}
    	}	
    	cout << ans << endl;
    	return 0;
    }

链接: [map用法][map].  
链接: [link][].

[map]: https://blog.csdn.net/shuzfan/article/details/53115922
[link]: https://www.csdn.net/