区间和问题――九度 155

区间和问题――九度 155

区间和问题――九度 155 篇1

题目描述：

给定一个数组，判断数组内是否存在一个连续区间，使其和恰好等于给定整数k，

输入：

输入包含多组测试用例，每组测试用例由一个整数n(1<=n<=10000)开头，代表数组的大小。

接下去一行为n个整数，描述这个数组，整数绝对值不大于100。

最后一行为一个整数k(大小在int范围内)。

输出：

对于每组测试用例，若存在这个连续区间，输出其开始和结束的位置，s，e(s <= e)。

若存在多个符合条件的输出，则输出s较小的那个，若仍然存在多个，输出e较小的那个。

若不存在，直接输出No。

样例输入：

5-1 2 3 -4 953-1 2 -372-1 10样例输出：

2 3No1 2思路：sum[i] 表示前i项和，题意即变为求是否存在 sum[i] - sum[j-1] == k，直接枚举无法通过。把式子转化一下可变为：sum[i] == sum[j-1] + k；题意又变为求是否存在一个sum[i] 使sum[j-1] + k == sum[i] 成立。这样直接过一遍就可以了。在不考虑前缀和相同的情况，用map标记就可以完成查找工作，如果存在前缀和相同的情况，用个vector容器跟每个前缀和对应就可以了。

#include#include#include#include