Java求区间和

 求区间和可以用到前缀和。前缀和可以通过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的区间和
        }
    }
}

打赏

微信扫一扫，打赏作者吧～