代码随想录刷题day07|（数组篇）58.区间和

一、数组理论基础

二、前缀和

三、相关算法题目

四、总结

五、待解决问题

一、数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合。

代码随想录 (programmercarl.com)

特点：

1.下标从0开始，内存中地址空间是连续的

2.查询快，增删慢

3.二维数组中，行为第一索引，列为第二索引

4.一旦创建以后，长度不能发生变化

5.元素无法删除，只能被覆盖

二、前缀和

前缀和在涉及计算数组区间和问题上是常用技巧，其主要思想是：计算出从下标0到下标 i（0< i < 数组长度）的数值之和p[i]，存放在另一数组p中，当需要计算某个区间和时，即可利用数组p得出结果，只需一个O（1）的操作，无需多次遍历元素数组，从而降低算法时间复杂度。

本题可以利用前缀和的思想，其中需要注意求解区间。例如，某一数组 array [1,2,3,4,5,6]，对应p数组为 [1,3,6,10,15,21]（p[0] = array[0]，p[1] = array[0] + array[1]...以此类推），现在要计算数组array下标2到下标5的数值之和（即：3,4,5,6的和:18），那么由p数组可知，应为：p[5] - p[1] = 21-3=18，而不是：p[5] - p[2]，因为p[2]是包含了下标2的（p[2]=p[0] + p[1] + p[2]），具体可参考下图：

图源代码随想录

三、相关算法题目

58.区间和

58. 区间和（第九期模拟笔试） (kamacoder.com)

两种方法：直接求和法和前缀和法

直接求和时间复杂度比较高，不推荐，暂不赘述。

前缀法：

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] Array = new int[n];
        int[] p = new int[n];
        int sum1 = 0;
        in.nextLine();
        int i = 0;
        while(in.hasNextInt() && i < n){
            Array[i] = in.nextInt();
            sum1 += Array[i];
            p[i] = sum1;
            in.nextLine();
            i++; //否则while成死循环 ⭐️
        }
        while(in.hasNextInt()){
            int a = in.nextInt();
            //in.nextLine();
            int b = in.nextInt();
            int sum2;
            if(a == 0){
                sum2 = p[b];
            }
            else{
                sum2 = p[b] - p[a-1];
            }
            System.out.println(sum2);
        }
        in.close();
    }
}