> 今日的每日一题：区域和检索-数组不可变
> 知识点总结：前缀和的应用
> 题目描述：题目很简单（虽然描述的有点令人看不懂）：求一个整数数组[i,j]的和（从i加到j，包含i，j）
> 我的解题思路：
1. 循环遍历 o(n)
2. 看到题目中有一个：“最多调用 104 次 sumRange 方法”，就觉得既然说到了要重复调用，那肯定是要调用，但是自己想到调用就只想到了递归…于是便用的递归：sumRange(i,j) = nums[i] + nums[j] + sumRange(i+1, j-1)。还不如循环…
> 官方给出的解题思路：利用前缀和。
（参考：https://leetcode-cn.com/problems/range-sum-query-immutable/solution/sha-shi-qian-zhui-he-ya-tu-jie-qian-zhui-0rla/）
# 前缀和数组sum的每一位记录的是 —— 起点到当前位置的连续一段的和，这样当我们求[i,j]这段区域和的时候，直接利用前缀和即可求解：sum[j]-sum[i-1]。
# 时间复杂度：预处理前缀和数组复杂度为O(n)，计算结果复杂度O(1)。
# 空间复杂度：存储前缀和数组sum的空间复杂度为O(n)。
> 总结：
1. 如何求前缀和？
sums[i] = sums[i-1] + nums[i] （动态规划）
2. 我是用js写的代码，看到思路之后，又自己写了一个，代码片段如下：
我的代码
然后提交结果是这样滴：
提交结果
官方提供的js代码：
官方代码
结果是这样滴：
结果
在我看来，觉得时间复杂度和空间复杂度是一样的啊，所以，关于数组的初始化（定长、不定长）、push函数需要深度学习一下。
网友评论