七的意志
方法1：前缀和+map \(O(nlogn)\)
题解：我们先进行前缀和，利用map记录每个前缀和出现的次数，要想区间和为7777，我们只要让\(ans+=mp[pre[i]-7777]\)即可，因为\(pre[j]+7777==pre[i]\)就能说明\([j+1,i]\)这个区间和为7777
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define endl '\n'
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 1e5 + 10;
ll pre[N] = {0};
map<ll, int> mp;
int main(void)
{
Zeoy;
int t = 1;
cin >> t;
while (t--)
{
mp.clear();
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
{
int x;
cin >> x;
pre[i] = pre[i - 1] + x;
mp[pre[i]]++;
}
ll ans = 0L;
for (int i = n; i >= 1; --i)
{
if (pre[i] == 7777)
ans++;
else if (pre[i] > 7777)
ans += mp[pre[i] - 7777];
}
cout << ans << endl;
}
return 0;
}
方法2：前缀和+二分\(O(nlogn)\)
题解：因为 \((1≤a_i≤5000)\)说明前缀和是单增的，我们可以利用其单增的性质查找有无\(pre[j]+7777==pre[i]\)的\(pre[i]\)
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;
int main(void)
{
Zeoy;
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
vector<ll> pre(n+2);
for (int i = 1; i <= n; ++i)
{
int x;
cin >> x;
pre[i] = pre[i - 1] + x;
}
ll ans = 0L;
for (int i = 1; i <= n; ++i)
{
if (binary_search(pre + i, pre + n + 1, pre[i - 1] + 7777))
ans++;
}
cout << ans << endl;
}
return 0;
}
方法3：双指针法\(O(n)\)
题解：因为 \((1≤a_i≤5000)\)说明前缀和是单增的，所以可以使用双指针，设区间左端点为\(l\)，右端点为\(r\)，开始时l,r都在最左边，如果sum<7777，右指针右移，如果sum>7777*,左指针右移，同时当右指针达到右边界时，我们只移动左指针，如果左指针的位置已经大于右指针，代表结束
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;
ll a[N] = {0};
int main(void)
{
Zeoy;
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
int l = 1, r = 1;
ll sum = a[1];
ll ans = 0L;
while (l <= r)
{
if (sum < 7777)
{
if (r < n)
{
r++;
sum += a[r];
}
else
break;
}
else if (sum > 7777)
{
sum -= a[l];
if (l <= r)
l++;
}
else if (sum == 7777)
{
ans++;
if (r < n)
{
r++;
sum += a[r];
}
else
{
sum -= a[l];
l++;
}
}
}
cout << ans << endl;
}
return 0;
}