题目描述
给定一个整数数组 nums，处理以下类型的多个查询:
- 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right
实现 NumArray 类：
- NumArray(int[] nums) 使用数组 nums 初始化对象
- int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + … + nums[right] )
示例 1：
提示：
- 1 <= nums.length <= 104
- -105 <= nums[i] <= 105
- 0 <= i <= j < nums.length
- 最多调用 104 次 sumRange 方法
题目解析
标准的前缀和问题，核心思路是用一个新的数组 preSum 记录 nums[0..i-1] 的累加和，看图 10 = 3 + 5 + 2：
看这个 preSum 数组，如果我想求索引区间 [1, 4] 内的所有元素之和，就可以通过 preSum[5] – preSum[1] 得出。
这样，sumRange 函数仅仅需要做一次减法运算，避免了每次进行 for 循环调用，最坏时间复杂度为常数 O(1)。
参考代码
以下为 Java 代码。
复杂度分析
- 时间复杂度：初始化 O(n)，每次检索 O(1)，其中 n 是数组 nums 的长度。
- 初始化需要遍历数组 nums 计算前缀和，时间复杂度是 O(n)。
- 每次检索只需要得到两个下标处的前缀和，然后计算差值，时间复杂度是 O(1)。
- 空间复杂度：O(n)，其中 n 是数组 nums 的长度。需要创建一个长度为 n+1 的前缀和数组。
