如何管理网站后台,保健品手机网站模板,网站托管维护代运营,制作网页的方法题干
难度#xff1a;简单
题目分析
题目要求算出每个指定区间内元素的总和。 然而#xff0c;区间在输入的最下面#xff0c;所以按照暴力破解的思路#xff0c;我们首先要遍历数组#xff0c;把它的值都存进去。 然后#xff0c;遍历下面的区间#xff0c;从索引a…题干
难度简单
题目分析
题目要求算出每个指定区间内元素的总和。 然而区间在输入的最下面所以按照暴力破解的思路我们首先要遍历数组把它的值都存进去。 然后遍历下面的区间从索引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个查询那时间复杂度就是Om*n)级别的有点太高了。
那么有没有更好的时间复杂度的方法呢
我们想到如果算区间和每次都从区间开始加到区间结束那么要把区间从头到尾遍历一遍。
有没有什么办法可以以O1级别的时间复杂度查询出区间和呢
解决办法就是————前缀和
简而言之就是创建一个数组存储累加之和。
比如新数组sumsum[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 all0;if (a 0) {all sum[b];} else {all sum[b] - sum[a-1]; //直接定位查询是O1级别的复杂度}System.out.println(all);}in.close();}
}
