---

E. Special Elements

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

题目：

样例：

cobol<br/>5<br/>9<br/>3 1 4 1 5 9 2 6 5<br/>3<br/>1 1 2<br/>5<br/>1 1 1 1 1<br/>8<br/>8 7 6 5 4 3 2 1<br/>1<br/>1<br/>

5 1 0 4 0

思路：

思维题，这里关键是  连续 这个方面，我们可以先统计一下 a数组相应的元素有多少个

然后利用 连续 的特征性质，遍历每个数组  元素 作为起点 往后累加，一旦大于该元素 停止累加，然后查找我们 连续累加 所得的对应结果，我们 a 数组里有没有出现过，累加答案即可

代码详解如下：

#include <iostream>
#include <unordered_map>
#define endl '\n'
#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>a, r;	// 这里是 a 数组 和 记忆数组

inline void solve()
{
	r.clear();	// 清空我们之前统计过的元素

	int n, ans = 0;
	cin >> n;
	for (int i = 0, x; i < n; ++i)
	{
		cin >> x;

		a[i] = x;

		r[x]++;	// 统计元素出现次数
	}

	for (int i = 0; i < n; ++i)
	{
		int sum = a[i];	//第 i 个元素作为起点
		for (int j = i + 1; j < n; ++j)
		{
			sum += a[j];	// 累加连续数组

			ans += r[sum];	// 答案累加统计出现的元素
			r[sum] = 0;		// 重新赋值初始化，省去下一次循环的初始化

			// 如果累加的元素超过了我们上限累加的范围，
			// 那么肯定不再存在，退出循环。
			// 这里 ai 的数据范围是   <= n ，所以最坏结果就是 n 个 n ，按道理来说累加上限就是  n * n
			// 但是题目给出的是

			// It is guaranteed that the sum of the values of n for all test cases in the input does not exceed 8000.

			// 也就是  n 个 ai 中连续累加 一定不超过  8000  ，又因为 2 <= n <= 8000  ,所以我们累加上限就是 n
			if (sum > n)
			{
				break;
			}

		}
		a[i] = 0;	// 初始化当前 a 数组的这个 元素
	}
	cout << ans << endl;
}


int main()
{
//	freopen("a.txt", "r", stdin);
	___G;
	int _t = 1;
	cin >> _t;
	while (_t--)
	{
		solve();
	}

	return 0;
}

最后提交：