Range Sum Query - Immutable
Range Sum Query - Immutable
卡尔曼和玻尔兹曼谁曼
发布于 2019-01-22 09:29:19
发布于 2019-01-22 09:29:19
303. Range Sum Query - Immutable
题目描述
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3Note:
- You may assume that the array does not change.
- There are many calls to sumRange function.
思路分析
题目中提示给定的nums数组不变，而且sumRange()函数可能需要多次被调用。
这个就很简单了，我们计算出来当前位置元素到初始元素之间所有元素之和，并进行存储，每次需要求解给定区间元素之和的时候收尾相减即可。这样就可以大大减少调用多次sumRange()函数的计算时间。
注意：我们的和元素组成的数组中第一个元素是0。
其实，我觉得这道题并不完全能算得上一道动态规划的题目。但是LeetCode把这道题归类到动态规划中也说得过去吧。
C++示例
class NumArray {
private:
vector<int> sums;
public:
NumArray(vector<int> nums) {
sums.push_back(0);
for (int i = 0; i < nums.size(); ++i) {
sums.push_back(nums[i] + sums[i]);
}
}
int sumRange(int i, int j) {
return sums[j + 1] - sums[i];
}
};
int main() {
vector<int> nums{-2, 0, 3, -5, 2, -1};
NumArray obj(nums);
int result = obj.sumRange(2, 5);
cout << result << endl;
return 0;
}Scala示例
object RangeSumQuery {
class NumArray(nums: Array[Int]) {
private val sums = new Array[Int](nums.length + 1)
for (i <- nums.indices)
sums(i + 1) = sums(i) + nums(i)
def sumRange(i: Int, j: Int): Int = {
sums(j + 1) - sums(i)
}
}
def main(args: Array[String]): Unit = {
val nums = Array(-2, 0, 3, -5, 2, -1)
val obj = new NumArray(nums)
val result = obj.sumRange(2, 5)
println(result)
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018年09月08日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录