#区间和

区间和

题目

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

输入描述

第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间，直至文件结束。

输出描述

输出每个指定区间内元素的总和。

==区间是一个左闭右闭区间==

思路

利用前缀和的思想，将中间结果存储到临时数组中。

• 输入数组时，同时构建前缀和数组（前缀和的构建区间：[0,i]）；
• [a,b]最后输出的实际上需要减去的是前一个闭区间：[a,b] = [0,b] – [0, a – 1]。

具体代码

Java

import java.util.*;

class Main {
    public static void main(String[] a) {
        Scanner scan = new Scanner(System.in);
        int len = scan.nextInt();
        int[] array = new int[len];
        int[] sum = new int[len + 1];
        for (int i = 0; i < len; i++) {
            array[i] = scan.nextInt();
            sum[i + 1] = array[i] + sum[i];
        }
        // 区间是左闭右闭
        while (scan.hasNextInt()) {
            int start = scan.nextInt();
            int end = scan.nextInt();
            System.out.println(sum[end + 1] - sum[start]);
        }
        scan.close();
    }
}