算法刷题-数组系列-卡码网.区间和

题目描述

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

示例：
输入：

5
1
2
3
4
5
0 1
1 3

输出:
3
9

要点

本题目以ACM的形式输入输出，与力扣的形式不一样，考察头文件的书写、数据结构的书写、主函数的书写等。

暴力解法（会超时）

直接输入数组然后遍历for一头一尾相加就行

前缀和

当多次查询重复区间的时候，采用前缀和，再创建一个数组，保存包含当前值及所有前面索引数组值的和，查询得时候直接arr[target_end]-arr[target_start-1]。避免每次都要for计算头到尾的进而优化代码。

代码

前缀和

int main(){int length = 0;int start = 0;int end = 0;cin >> length;vector <int> arr(length);vector<int> presum(length);int presums = 0;for(int i = 0; i < length; i++){cin >> arr[i];presums+=arr[i];presum[i] =presums;}while(cin >> start >> end){int sum = 0;if (start==0) {sum = presum[end];}else{sum = presum[end]-presum[start-1];}cout << sum << endl;}return 0;
}

暴力解法

//暴力解法，可以但可能会被卡掉
// int main(){//     int length = 0;
//     int start = 0;
//     int end = 0;//     cin >> length;
//     vector <int> arr(length);
//     for(int i = 0; i < length; i++){
//         cin >> arr[i];
//     }
//     while(cin >> start >> end){
//         int sum = 0;
//         for(int i = start;i<=end;i++) sum+=arr[i];
//         cout << sum << endl;
//     }
//     return 0;
// }