weiyuchen4510 @ 2024-11-11 20:15:57
题目： 说明 整数数列a[1], a[2]，......，a[n] (有正有负) ，以及另一个整数k，求一个区间[i,j]， (1≤i≤j≤n)，使得a[ i ]+...+a[j]=k。 输入格式 第1行: 2个数n,k。n为数列的长度。k为需要求的和。(2≤n≤1000000，-10^9≤ k≤10^9) 第2-n+1行: a[i](-10^9≤a[ i ]≤10^9)。
输出格式 如果没有这样的序列输出No Solution。 输出2个数i,j，分别是区间的起始和结束位置。如果存在多个，输出i最小的。如果i相等，输出j最小的。
回答必关
by sxwgysh @ 2024-11-11 20:36:23
@weiyuchen4510 你看看这个行不行（我是蒟蒻）
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6 + 10;
int n, k;
vector<ll> a(N);
signed main()
{
cin >> n >> k;
for (int i = 1; i <= n; ++ i)
cin >> a[i];
unordered_map<ll, int> sum;
ll ans = 0;
sum[0] = 0;
for (int j = 1; j <= n; ++ j)
{
ans += a[j];
if (sum.find(ans - k) != sum.end())
{
int i = sum[ans - k] + 1;
cout << i << " " << j << "\n";
return 0;
}
if (sum.find(ans) == sum.end()) sum[ans] = j;
}
cout << "No Solution" << "\n";
return 0;
}by weiyuchen4510 @ 2024-11-11 21:01:37
@sxwgysh 王说了，要用map
by weiyuchen4510 @ 2024-11-11 21:02:15
忘
by sxwgysh @ 2024-11-11 21:14:21
@weiyuchen4510 我觉得这两个应该是一样的吧，unordered_map是不排序的，map是排序的（我不知道啊）
by weiyuchen4510 @ 2024-11-11 21:16:31
@sxwgysh O我刚刚没看到
by weiyuchen4510 @ 2024-11-11 21:17:08
@sxwgysh 已关谢谢