九度 1554：区间问题

题目描述：

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

 

输入：

输入包含多组测试用例，每组测试用例由一个整数n(1<=n<=10000)开头，代表数组的大小。
接下去一行为n个整数，描述这个数组，整数绝对值不大于100。
最后一行为一个整数k(大小在int范围内)。

 

输出：

对于每组测试用例，若存在这个连续区间，输出其开始和结束的位置，s，e(s <= e)。
若存在多个符合条件的输出，则输出s较小的那个，若仍然存在多个，输出e较小的那个。
若不存在，直接输出"No"。

 

样例输入：

5
-1 2 3 -4 9
5
3
-1 2 -3
7
2
-1 1
0

样例输出：

2 3
No
1 2

思路

1. o(n^n) 复杂度算法超时

2. 正解. D[i] 记录 0~i 的和, 若 D[j] - D[i] == k, 那么 i~j 是一个可行解. 对 D[i] 进行索引排序后枚举 i 并使用二分查找 j. 时间复杂度为 o(nlogn)

代码

九度 1554：区间问题,布布扣,bubuko.com

九度 1554：区间问题

原文：http://www.cnblogs.com/xinsheng/p/3606186.html