来源:力扣 (LeetCode)
链接:https://leetcode-cn.com/problems/range-sum-query-immutable
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
一、题目描述
给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。
示例:
给定 nums = [-2, 0, 3, -5, 2, -1],求和函数为 sumRange() 。
1 2 3 |
sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3 |
说明:
- 你可以假设数组不可变。
- 会多次调用 sumRange 方法。
二、题解
题目很迷幻,一眼看上去可能会误解成就是求指定区间的和,如果只是求指定区间内的和,除了遍历就没有其他办法了。而实际上整道题目的重点就是会多次调用,也就是说同一份数据,会有多个测试案例。
很容易能猜出最容易出现问题的地方就是超时了,因为实际的问题很简单,就是求和,求和只能遍历,不可能就这么简单每次就遍历求和。因此考虑的重点就在于如何在多次调用中减少时间占用。
减少计算时间的办法:缓存数据,即缓存下来部分数据的和,再根据缓存的和来计算特定范围的和。
以测试数据为例,以 sum[i] 表示下标 i 以前 (不包括 i)的所有数据之和,那么 sum 数组的值为:
1 |
0, -2, -2, 1, -4, -2, -3 |
sumRange(0, 2) 就相当于计算 sum[2 + 1] - sum[0] ,值为 1 。
sumRange(2, 5) 就相当于计算 sum[5 + 1] - sum[2],值为-2 。
在这种情况下能总结出来的规律是:sumRange(i, j) = sum[j + 1] - sum[i] 。
三、代码
逻辑很简单,但关键点是:sum[i] 表示的是 i 以前所有元素的和,所以要给 sum[0] 赋值上一个 0 值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
class NumArray { private: vector<int> sum; public: NumArray(vector<int>& nums) { // 构造函数中初始化 sum 数组 size_t i; // 给 sum[0] 附上一个 0 值 sum.push_back(0); for (i = 0; i< nums.size(); i++) { sum.push_back(sum[i] + nums[i]); } } int sumRange(int i, int j) { return sum[j + 1] - sum[i]; } }; |
优化
可以看到,时间消耗还是很大的,排名才击败了 38% 。代码中主要的耗时是 vector 数组的扩容导致的,因为够早的时候需要频繁 push_back 导致数组扩容和内存拷贝,比较费时。可以把 vector 改成数组形式,手动分配内存空间,减少 vector 频繁扩容。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class NumArray { private: int *sum; public: NumArray(vector<int>& nums) { size_t i; sum = new int[nums.size() + 1]; sum[0] = 0; for (i = 0; i< nums.size(); i++) { sum[i + 1] = sum[i] + nums[i]; } } int sumRange(int i, int j) { return sum[j + 1] - sum[i]; } }; |
重新提交后,时间消耗击败了 86% 的用户。
评论