当前位置:网站首页>leetcode-303:区域和检索 - 数组不可变
leetcode-303:区域和检索 - 数组不可变
2022-07-07 08:18:00 【菊头蝙蝠】
题目
给定一个整数数组 nums,处理以下类型的多个查询:
- 计算索引 left 和 right (包含 left 和 right)之间的 nums 元素的 和 ,其中 left <= right
实现 NumArray 类:
- NumArray(int[] nums) 使用数组 nums 初始化对象
- int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ,包含 left 和 right 两点(也就是 nums[left] + nums[left + 1] + … + nums[right] )
示例 1:
输入:
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出:
[null, 1, -1, -3]
解释:
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))
解题
方法一:前缀和
s[i]=nums[0]+nums[1]+....+nums[i-1];
如果要求 nums[2]+nums[3]+nums[4]
只需要
求s[4]-s[1]
即可。
因此可以在初始化的时候,就去计算出每个s[i]
的值
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];
}
};
边栏推荐
- 学习记录——高精度加法和乘法
- STM32 Basics - memory mapping
- Es classes and objects, prototypes
- HDU-2196 树形DP学习笔记
- Study summary of postgraduate entrance examination in November
- 01 use function to approximate cosine function (15 points)
- C logging method
- Word自动生成目录的方法
- When there are pointer variable members in the custom type, the return value and parameters of the assignment operator overload must be reference types
- ORM -- grouping query, aggregation query, query set queryset object properties
猜你喜欢
Appx代码签名指南
【acwing】789. 数的范围(二分基础)
Talking about the return format in the log, encapsulation format handling, exception handling
Programming features of ISP, IAP, ICP, JTAG and SWD
搭建物联网硬件通信技术几种方案
This article explains the complex relationship between MCU, arm, muc, DSP, FPGA and embedded system
The physical meaning of imaginary number J
Es classes and objects, prototypes
ORM model -- creation and query of data records
STM32 ADC and DMA
随机推荐
Several schemes of building hardware communication technology of Internet of things
【华为机试真题详解】高矮个子排队
Encrypt and decrypt stored procedures (SQL 2008/sql 2012)
IPv4 socket address structure
[learning notes - Li Hongyi] Gan (generation of confrontation network) full series (I)
Review of the losers in the postgraduate entrance examination
Use of JSON extractor originals in JMeter
Study summary of postgraduate entrance examination in September
搭建物联网硬件通信技术几种方案
Appx代碼簽名指南
根据设备信息进行页面跳转至移动端页面或者PC端页面
Postman interface test III
OpenGL glLightfv 函数的应用以及光源的相关知识
The story of Plato and his three disciples: how to find happiness? How to find the ideal partner?
[higherhrnet] higherhrnet detailed heat map regression code of higherhrnet
对存储过程进行加密和解密(SQL 2008/SQL 2012)
Chris LATTNER, the father of llvm: why should we rebuild AI infrastructure software
1324:【例6.6】整数区间
XML configuration file parsing and modeling
Study summary of postgraduate entrance examination in August