2021-03-01 知识点：一维前缀和的应用

> 今日的每日一题：区域和检索-数组不可变

> 知识点总结：前缀和的应用

> 题目描述：题目很简单（虽然描述的有点令人看不懂）：求一个整数数组[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函数需要深度学习一下。