---

E1. Array and Segments (Easy version)

原创 于 2023-08-29 17:00:30 发布 · 粉丝可见 · 106 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132564134

题目：

样例：

cobol<br/>3<br/>3<br/>120<br/>5<br/>11011<br/>6<br/>600005<br/>

3 6 1

题意：

题目意思是，找出有该数组中，有多少个子数组是   元素之和等于该子数组长度

思路：

在这里，我们可以弄个偏移量 -1 ，

比如 当 子数组a 为  a = 【1】    那么  1 - 1 == 0   则  sum = 1 - 1 = 0  当 sum == 0 的时候ans++

反之不是。

代码详解如下：

#include <iostream>
#include <unordered_map>
#define endl '\n'
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
umap<int, int>r;	// 记录 每个子数组中
 
inline void solve()
{
	r.clear();
	string s;
	int n, ans = 0;
	cin >> n;
	getchar();
	getline(cin, s);
	int sum = 0;
	for (int i = 0; i < n; ++i)
	{
		// 这里是记录该数组是否满足 sum == 0
		// 即满足数组元素之和等于数组长度
		sum += (s[i] - '0' - 1);
 
		// 如果满足 ans++
		if (!sum)
			ans++;
 
		// 累加子数组满足 sum == 0 的
		ans += r[sum];
 
		// 记录满足子数组个数
		++r[sum];
	}
	cout << ans << endl;
}
 
 
signed main()
{
//	freopen("a.txt", "r", stdin);
//	___G;
	int _t = 1;
	cin >> _t;
	while (_t--)
	{
		solve();
	}
 
	return 0;
}

最后提交：

​​​​​​​