[leetcode]303-区域和检索(数组不可变)

有空一起学习 2020年2月9日17:10:14 发表评论

来源:力扣(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. 会多次调用 sumRange 方法。

二、题解

题目很迷幻,一眼看上去可能会误解成就是求指定区间的和,如果只是求指定区间内的和,除了遍历就没有其他办法了。而实际上整道题目的重点就是会多次调用,也就是说同一份数据,会有多个测试案例。

很容易能猜出最容易出现问题的地方就是超时了,因为实际的问题很简单,就是求和,求和只能遍历,不可能就这么简单每次就遍历求和。因此考虑的重点就在于如何在多次调用中减少时间占用。

减少计算时间的办法:缓存数据,即缓存下来部分数据的和,再根据缓存的和来计算特定范围的和。

以测试数据为例,以sum[i]表示下标i以前(不包括i)的所有数据之和,那么sum数组的值为:

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值。

[leetcode]303-区域和检索(数组不可变)

优化

可以看到,时间消耗还是很大的,排名才击败了38%。代码中主要的耗时是vector数组的扩容导致的,因为够早的时候需要频繁push_back导致数组扩容和内存拷贝,比较费时。可以把vector改成数组形式,手动分配内存空间,减少vector频繁扩容。

重新提交后,时间消耗击败了86%的用户。

本文共执行69次查询,耗时0.600秒!
历史上的今天
二月
9
有空一起学习

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: