leetcode 代码随想录 数组-区间和

题目

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

• 输入：
  1. 第一行输入：为整数数组 Array 的长度 n，
  2. 接下来 n 行，每行一个整数，表示数组的元素。
  3. 随后的输入为需要计算总和的区间，直至文件结束。
• 输出：
  • 输出每个指定区间内元素的总和。

思路 & 代码

前缀和

统计 vec[i] 数组上的区间和

• 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];

#include <iostream>
#include <vector>
using namespace std;int main(){int n, a, b;cin >> n;vector<int> nums(n);vector<int> pre(n);int presum = 0;for(int i = 0; i < n; i++){scanf("%d",&nums[i]);presum += nums[i];pre[i] = presum;}while(scanf("%d%d", &a, &b) == 2) {int sum;if(a == 0){sum = pre[b];}else{sum = pre[b] - pre[a - 1];}printf("%d\n",sum);}
}

总结

• 输入一个元素：scanf(“%d”,&a);
• 输入二个元素：scanf(“%d%d”, &a, &b);
• 打印：printf(“%d\n”,sum);