素材网站设计,网站开发中 即将上线,免费发布信息有哪些网站,知名建站的公司本博文为《代码随想录》学习笔记#xff0c;原文链接#xff1a;代码随想录 题目
原题链接#xff1a;58. 区间和#xff08;第九期模拟笔试#xff09;
题目描述
给定一个整数数组 Array#xff0c;请计算该数组在每个指定区间内元素的总和。
输入描述
第一行输入为…本博文为《代码随想录》学习笔记原文链接代码随想录 题目
原题链接58. 区间和第九期模拟笔试
题目描述
给定一个整数数组 Array请计算该数组在每个指定区间内元素的总和。
输入描述
第一行输入为整数数组 Array 的长度 n接下来 n 行每行一个整数表示数组的元素。随后的输入为需要计算总和的区间下标ab b a直至文件结束。
输出描述
输出每个指定区间内元素的总和。
输入示例
5
1
2
3
4
5
0 1
1 3
输出示例
3
9
提示信息
数据范围 0 n 100000
题解
方法一暴力解法
注意**处代码的写法之前没有这样写过
#include bits/stdc.h
using namespace std;int main()
{int n,a,b; cinn;int nums[n];for(int i0;in;i){cinnums[i];}while(cinab)//** 注意这里的写法{int sum0;for(int ia;ib;i)sumnums[i];coutsumendl;}return 0;
}
vector初始化
这里纠正之前关于vector的一个误区vector初始化的方式有以下几种 1、定义空向量 vectorint a; //相当于空数组 2、定义具有10个整型元素的向量 vectorint a(10); //相当于a[10] 3、定义具有10个整型元素的向量且赋予每个元素初值为1 vectorint a(10,1); //相当于a[10] {1} 4、定义与向量b具有相同值的向量a vectorint a(b); //将向量b赋值给向量a即向量a等于向量b 5、将向量b中下标0-2共三个的元素赋值给a //第一个数据是起始地址第二个数据是结束地址不包括第二个数据就是你要截取的长度加1 vectorint a(b.begin(), b.begin()3); 6、从数组中获得初值 int b[7] {1,2,3,4,5,6,7}; //定义整形数组 vectorint a(b, b7; //将数组b赋值给a第一个数据是起始地址第二个数据是结束地址不包括 7、二维数组初始化 vectorvectorint a; //初始化为int型二维数组相当于int a[][] 下标只能获取已存在的元素所以以下赋值方法对第一种初始化方法是错误的
for(int i0; i10; i){a[i] i; //应使用a.push_back(i)
}
但当数组中已经存在元素则可以使用上述方法进行赋值因此方法一还可以写成如下形式
#include iostream
#include vector
using namespace std;
int main() {int n, a, b;cin n;vectorint vec(n);for (int i 0; i n; i) cin vec[i];while (cin a b) {int sum 0;// 累加区间 a 到 b 的和for (int i a; i b; i) sum vec[i];cout sum endl;}
}
提交代码发现超时了 当查询范围和查询次数较大时这种暴力解法的时间复杂度时非常大的。
方法二前缀和方法
对前缀和的思路进行举例说明例如我们要统计vec[i]这个数组上的区间和。
我们先做累加即p[i]表示下标0到i的vec[i]累加之和。如图 如果我们想统计在vec数组上 下标 2 到下标 5 之间的累加和那就用 p[5] - p[1] 就可以了。
p[1] vec[0] vec[1];
p[5] vec[0] vec[1] vec[2] vec[3] vec[4] vec[5];
p[5] - p[1] vec[2] vec[3] vec[4] vec[5]; p[5] - p[1] 就是 红色部分的区间和。
而 p 数组是我们之前就计算好的累加和所以后面每次求区间和的之后 我们只需要 O(1) 的操作。
特别注意 在使用前缀和求解的时候要特别注意 求解区间。
如上图如果我们要求 区间下标 [2, 5] 的区间和那么应该是 p[5] - p[1]而不是 p[5] - p[2]。在解题时可以通过画图来帮助理解。
编写代码如下
#include bits/stdc.h
using namespace std;int main()
{int n,a,b; cinn;int nums[n];int p[n];//前缀和数组 for(int i0;in;i){cinnums[i];p[i]p[i-1]nums[i];}while(cinab){int sump[b]-p[a-1];coutsumendl;}return 0;
} 《代码随想录》中给出的代码如下
#include iostream
#include vector
using namespace std;
int main() {int n, a, b;cin n;vectorint vec(n);vectorint p(n);int presum 0;for (int i 0; i n; i) {cin vec[i];presum vec[i];p[i] presum;}while (cin a b) {int sum;if (a 0) sum p[b];else sum p[b] - p[a - 1];cout sum endl;}
}C 代码 面对大量数据 读取 输出操作最好用scanf 和 printf耗时会小很多
#include iostream
#include vector
using namespace std;
int main() {int n, a, b;cin n;vectorint vec(n);vectorint p(n);int presum 0;for (int i 0; i n; i) {scanf(%d, vec[i]);presum vec[i];p[i] presum;}while (~scanf(%d%d, a, b)) {int sum;if (a 0) sum p[b];else sum p[b] - p[a - 1];printf(%d\n, sum);}
}
