算法之区间和题目讲解

题干

难度：简单

题目分析

题目要求算出每个指定区间内元素的总和。
然而，区间在输入的最下面，所以按照暴力破解的思路，我们首先要遍历数组，把它的值都存进去。
然后，遍历下面的区间，从索引a到b，累加元素。
根据这个思路，我们会发现，暴力破解的代码如下：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 读取数组的长度int len = in.nextInt();int[] s = new int[len];// 读取数组元素for (int i = 0; i < len; i++) {s[i] = in.nextInt();}// 读取区间并计算和while (in.hasNextInt()) {int a = in.nextInt();int b = in.nextInt();int sum = 0;// 暴力计算区间和for (int i = a; i <= b; i++) {sum += s[i];}// 输出结果System.out.println(sum);}in.close();}
}

我们分析一下这样写的时间复杂度。

假设数组长度为n，有m个查询，那时间复杂度就是O（m*n)级别的，有点太高了。

那么，有没有更好的时间复杂度的方法呢？

我们想到，如果算区间和，每次都从区间开始加到区间结束，那么要把区间从头到尾遍历一遍。

有没有什么办法，可以以O（1）级别的时间复杂度查询出区间和呢？

解决办法就是————前缀和

简而言之，就是创建一个数组，存储累加之和。

比如新数组sum，sum[0]代表s[0]，sum[1]代表s[0]+s[1]，sum[2]代表s[0]+s[1]+s[2]

这样我们如果需要s[1]+s[2]，只需要用sum[2]-sum[0]就行

代码

根据这个思路，我们编写代码

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int len = in.nextInt();int[] s = new int[len];for (int i = 0; i < len; i++) { //存储数组的值s[i] = in.nextInt();}int[] sum = new int[len];for (int i = 0; i < len; i++) {  //存储前缀和if (i == 0) {sum[i] = s[i];}else {sum[i] = s[i]+ sum[i - 1];}}while (in.hasNextInt()) {int a = in.nextInt();int b = in.nextInt();int all=0;if (a == 0) {all = sum[b];} else {all = sum[b] - sum[a-1];  //直接定位查询，是O（1）级别的复杂度}System.out.println(all);}in.close();}
}