P214. 不可变数组的区间和查询

leetcode 303 lintcode 943 数组 动态规划 讨论

温馨提示:您没有权限查看当前视频。 立即购买观看视频

描述

这个题目说的是,给你一个不为空的整数数组,你要设计一个类,可以高效地查询数组中下标从 i 到 j 的区间和。

注意,你可以假设数组一旦给你,就不会发生改变。并且给你的 i 和 j 一定是合法的下标,总是可以求出有效的区间和。另外,求区间和的函数会被频繁调用。

比如说,给你的数组 a 是:

-1, 0, 4, -2, 8

假设计算区间和的函数是 f,那么有:

f(0, 1) = -1 + 0 = -1
f(1, 3) = 0 + 4 + (-2) = 2

关于 AlgoCasts

AlgoCasts 旨在用心做好每一个算法讲解视频。每个视频包含两个部分:题目的剖析讲解以及编码,力求在讲解清楚到位的基础上,尽可能地保持视频精简短小,让大家可以在碎片时间里进行学习,并收获这些算法题背后的思想与乐趣。