当前位置:网站首页>Leetcode-303: region and retrieval - array immutable
Leetcode-303: region and retrieval - array immutable
2022-07-07 10:27:00 【Chrysanthemum headed bat】
leetcode-303: Area and retrieval - The array is immutable
subject
Given an array of integers nums, Handle multiple queries of the following types :
- Calculation index left and right ( contain left and right) Between nums Elemental and , among left <= right
Realization NumArray class :
- NumArray(int[] nums) Using arrays nums Initialize object
- int sumRange(int i, int j) Returns an array of nums Middle index left and right Between elements The sum of the , contain left and right At two o 'clock ( That is to say nums[left] + nums[left + 1] + … + nums[right] )
Example 1:
Input :
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
Output :
[null, 1, -1, -3]
explain :
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1))
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
Problem solving
Method 1 : The prefix and
s[i]=nums[0]+nums[1]+....+nums[i-1];
If required nums[2]+nums[3]+nums[4]
It only needs
seek s[4]-s[1]
that will do .
So you can initialize , Just calculate each s[i]
Value
class NumArray {
public:
vector<int> sums;
NumArray(vector<int>& nums) {
int n=nums.size();
sums.resize(n+1);
for(int i=1;i<=nums.size();i++){
sums[i]=sums[i-1]+nums[i-1];
}
}
int sumRange(int left, int right) {
return sums[right+1]-sums[left];
}
};
边栏推荐
- Word自动生成目录的方法
- openinstall与虎扑达成合作,挖掘体育文化产业数据价值
- The variables or functions declared in the header file cannot be recognized after importing other people's projects and adding the header file
- 1323:【例6.5】活动选择
- . Net configuration system
- The Hal library is configured with a general timer Tim to trigger ADC sampling, and then DMA is moved to the memory space.
- SQLyog数据库怎么取消自动保存更改
- CONDA creates virtual environment offline
- 关于hzero-resource报错(groovy.lang.MissingPropertyException: No such property: weight for class)
- XML configuration file parsing and modeling
猜你喜欢
String formatting
字符串格式化
Remote meter reading, switching on and off operation command
P2788 数学1(math1)- 加减算式
【acwing】789. 数的范围(二分基础)
嵌入式背景知识-芯片
The request object parses the request body and request header parameters
The Hal library is configured with a general timer Tim to trigger ADC sampling, and then DMA is moved to the memory space.
每周推荐短视频:L2级有哪些我们日常中经常会用到的功能?
JMeter about setting thread group and time
随机推荐
SQLyog数据库怎么取消自动保存更改
Remote meter reading, switching on and off operation command
施努卡:机器人视觉抓取工作原理 机器视觉抓取
对word2vec的一些浅层理解
Appx代碼簽名指南
Fiddler break point
2022.7.5DAY597
Embedded background - chip
Inno Setup 打包及签名指南
IPv4 socket address structure
柏拉图和他的三个弟子的故事:如何寻找幸福?如何寻找理想伴侣?
Pdf document signature Guide
ArcGIS operation: converting DWG data to SHP data
CONDA creates virtual environment offline
String formatting
How embedded engineers improve work efficiency
Study summary of postgraduate entrance examination in September
Review of the losers in the postgraduate entrance examination
BigDecimal数值比较
Appx code signing Guide