0058.区间和.md

58. 区间和

题目链接

C

C++

//前缀和的应用
#include<bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 10;
 
int n,a[N], sum[N],L,R;
 
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]), sum[i] =sum[i - 1] + a[i];
    while(~scanf("%d%d", &L, &R)){
        printf("%d\n", sum[R + 1] - sum[L]);
    }
    return 0;
}

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();

        int[] numberArray = new int[size];
        for (int i = 0; i < size; i++) {
            numberArray[i] = scanner.nextInt();
        }

        // 计算前缀和数组
        int[] prefixArray = new int[size];
        prefixArray[0] = numberArray[0];
        for (int i = 1; i < numberArray.length; i++) {
            prefixArray[i] = prefixArray[i - 1] + numberArray[i];
        }
        // 计算区间和
        while (scanner.hasNextInt()) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            System.out.println(calculateRangeSum(prefixArray, start, end));
            // System.out.println(calculateRangeSum2(numberArray, start, end));
        }
    }

    // 使用前缀和的方法
    public static int calculateRangeSum(int[] array, int start, int end) {
        int prefixSumStart = (start > 0) ? array[start - 1] : 0;
        return array[end] - prefixSumStart;
    }

    // // 原始的方法
    // public static int calculateRangeSum2(int[] array, int start, int end) {
    //     int tmp = 0;
    //     for (int i = start; i < end + 1; i++) {
    //         tmp += array[i];
    //     }
    //     return tmp;
    // }
}

Python

JS

Go