51Nod 和为k的连续区间

一整数数列a1, a2, ... , an（有正有负），以及另一个整数k，求一个区间[i, j]，(1 <= i <= j <= n)，使得a[i] + ... + a[j] = k。

Input

第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)。

Output

如果没有这样的序列输出No Solution。
输出2个数i, j，分别是区间的起始和结束位置。如果存在多个，输出i最小的。如果i相等，输出j最小的。

Input示例

6 10
1
2
3
4
5
6

Output示例

1 4
数据小时，可以暴力，效率比较高的是用map储存前缀和的位置

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <ctime>
#include <map>
#include <set>
using namespace std;
#pragma comment(linker, "/stck:1024000000,1024000000")
#define lowbit(x) (x&(-x))
#define max(x,y) (x>=y?x:y)
#define min(x,y) (x<=y?x:y)
#define MAX 100000000000000000
#define MOD 1000000007
#define pi acos(-1.0)
#define ei exp(1)
#define PI 3.1415926535897932384626433832
#define ios() ios::sync_with_stdio(true)
#define INF 0x3f3f3f3f
#define mem(a) ((a,0,sizeof(a)))
typedef long long ll;
ll a[10006]={0},n,k;
map<ll,int>m;
int main()
{
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        a[i]+=a[i-1];
    }
    for(int i=n;i;i--)
        m[a[i]]=i;
    int flag=0,l,r;
    for(int i=1;i<=n;i++)
    {
        if(a[i]-k==0 || m[a[i]-k])
        {
            if(!flag && m[a[i]-k]+1<=i) {l=m[a[i]-k]+1;r=i;flag^=1;}
            else if(flag && m[a[i]-k]+1<=i)
            {
                if(m[a[i]-k]+1<l) {l=m[a[i]-k]+1;r=i;}
                else if(m[a[i]-k]+1==l) r=min(r,i);
            }
        }
    }
    if(!flag) printf("No Solution
");
    else printf("%d %d
",l,r);
    return 0;
}