区间和问题――九度 1554 - c++编程基础

题目描述：

给定一个数组，判断数组内是否存在一个连续区间，使其和恰好等于给定整数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

思路：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
                #include 
                
                  #define M 10010 #define OFFSET 1000000 #define MIN(x, y) ((x) < (y) ? (x) : (y)) int sum[M]; using namespace std; vector
                 
                  cnt[M]; int main() { //freopen(in.txt, r, stdin); int n; int i, j, k, a, t, s, u; while(~scanf(%d, &n)) { u = 1; map
                  
                   vis; memset(sum, 0, sizeof(sum)); for(i=0; i
                   
                     OFFSET){ printf(No ); continue; } int left = 0, right = 0; int flag = 0; for(i=1; i<=n; i++){ t = sum[i-1] + k; if(vis[t]){ int b = vis[t]; for(j=0; j
                    
                     = i){ flag = 1; left = i; right = cnt[b][j]; break; } } if(flag) break; } } if(flag) printf(%d %d , left, right); else printf(No ); for(i=0; i
                     
                      ?
                      ?
                      ?
                      ?