51nod-- 1094 和为k的连续区间

题目描述

基准时间限制：1 秒 空间限制：131072 KB 分值: 10 难度：2级算法题 收藏  关注
一整数数列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

解题思想

/*
 题目是求连续区间和，第一反应想到三层循环，
 然后看数据量是1e4，说明至少需要n^2的时间复杂度，于是便想到了之前做的一道题，
 s[i] = a[0] + ... a[i]
 s[j] = a[0]+ ..+ a[i] +..+ a[j]
 所以a[i]+a[i+1]...+ a[j] = s[j] - s[i-1]
 于是就满足时间复杂度的条件了
*/

代码

import java.util.Scanner;
public class  Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        //init
        int[] a = new int[n+1];
        long[] sum = new long[n+1];
        sum[0] = 0;
        a[0] = 0;
        boolean flag = true;
        //input
        for(int i=1; i<=n; ++i){
            a[i] = sc.nextInt();
            sum[i] = a[i]+ sum[i-1]; 
        }
        //process 
        for(int i=1; i<n; ++i)
          for(int j=i; j<n; ++j){
              if(k == sum[j]-sum[i-1]){
                  System.out.println(i+" "+ j);
                  flag = false;
                  return;
              }
          }

        if(flag)
           System.out.println("No Solution");
    }
}