Java求区间和

时间:2022-02-22作者:klpeng分类:IT综合浏览:370评论:0

 求区间和可以用到前缀和。前缀和可以通过O(1)的算法复杂度来求一个区间的和。设 q为一个数组,用S来存储q数组对应下标的前n项和。如果要求下标n~m区间的q数组的和。就是用 S[m]-S[n-1] 来得到,用前m项的和S[m]减去前n-1项的和,从而得到区间m~n的和。如S[3]里的值指的是q数组前3项的和
 代码实例:
 输入n,m。输入n个数。然后输入m个x,y。输出x~y的区间和。

import java.util.*;

public class Main{
    
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int q[] = new int[n+1]; //q数组存元素
        int S[] = new int[n+1]; //S数组每个下标n ,存储q数组前n项的和
        for(int i = 1;i<=n;i++){
            q[i] = sc.nextInt();
            S[i] += S[i-1]+q[i];
        }
        while(m-->0){
            int x = sc.nextInt();
            int y = sc.nextInt();
            System.out.println( S[y]-S[x-1] ); //使用S[y]-S[x-1]求 y~x的区间和
        }
    }
}
打赏
文章版权声明:除非注明,否则均为彭超的博客原创文章,转载或复制请以超链接形式并注明出处。
相关推荐

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

猜你喜欢