数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会学
时尚学
法学范围求和查询——不可变的 C++
假设我们有一个整数数组。我们必须找到从索引 i 到 j 中的元素之和。我们需要记住两件事：一是数组不可变，因此不会更改元素；二是此类查询会有很多。因此，我们必须考虑大量查询的执行时间。假设数组类似于 A = [5, 8, 3, 6, 1, 2, 5]，则如果查询为 (A, 0, 3)，则其结果应为 5 + 8 + 3 + 6 = 22。
为了解决此问题，我们将按照以下步骤操作：
- 选择一个数组 B。B[i] 将存储从 0 到 i 的元素之和。
- 对于查询，执行 B[j] – B[i – 1]
让我们了解以下实施，以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class NumArray {
public:
vector <int> pre;
NumArray(vector<int>& nums) {
pre.clear();
int n = nums.size();
pre.resize(n);
for(int i = 0; i < n; i++){
if(i == 0)pre[0] = nums[0];
else
pre[i] = pre[i - 1] + nums[i];
}
}
int sumRange(int i, int j) {
if(i == 0)return pre[j];
return pre[j] - pre[i - 1];
}
};
main(){
vector<int> v = {5,8,3,6,1,2,5};
NumArray na(v);
cout<<na.sumRange(0,2)<<endl;
cout<<na.sumRange(2,5)<<endl;
cout<<na.sumRange(0,5)<<endl;
}输入
Initialize it with [5,8,3,6,1,2,5] Call sumRange(0,2) sumRange(2,5) sumRange(0,5)
输出
16 12 25
更新于： 2020-4-28
118 次浏览
广告