3738 - 和为 k 的连续区间
描述
给定一整数数列 a1, a2, ..., an(有正有负),以及另一个整数 k,求一个区间 [i, j](1 <= i <= j <= n),使得 a[i] + ... + a[j] = k。
输入
第 1 行:2 个数 N, K。N 为数列的长度,K 为需要求的和。(2 <= N <= 10000,-10^9 <= K <= 10^9)

第 2 ~ N+1 行:A[i](-10^9 <= A[i] <= 10^9)。
输出
如果没有这样的序列输出 No Solution。

否则输出 2 个数 i, j,分别是区间的起始和结束位置。如果存在多个,输出 i 最小的。如果 i 相等,输出 j 最小的。
样例

输入

6 5
1
2
3
4
5
6

输出

2 3
提示
记前缀和 S[0]=0,S[i] = a[1] + ... + a[i],则区间 [i, j] 的和为 k 等价于 S[j] - S[i-1] = k,即 S[i-1] = S[j] - k。

用哈希表(或 map)记录每个前缀和第一次出现的位置。从左到右枚举右端点 r,若 S[r] - k 曾经出现过,就得到一个候选区间;在所有候选中取 i 最小、i 相同时 j 最小的即可。注意前缀和可能超过 int 范围,需要使用 long long。
来源
51nod 1094
标签
题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 1
通过次数 1