303. 区域和检索 - 数组不可变

303. 区域和检索 - 数组不可变

给定一个整数数组 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：

输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出：
[null, 1, -1, -3]解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1)) 
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

提示：

• $1<=nums.length<=10^4$
• $-10^5<=nums[i]<=10^5$
• $0<=i<=j<nums.length$
• 最多调用 $10^4$ 次 sumRange 方法

思路：(前缀和)

根据数学层面可以这样理解：

代码理解： 前缀和数组 sums[i]里面存的就是原数组num的前 i 项和，例如sums[2] 这里面存的就是原数组num的前2项和

而数组最大的优点就是便于可以直接根据索引查找，前缀和就是充分运用了数组这个优点，只要理解了前缀和这个概念，代码的思路其实很简单 思路：
1、首先创建一个前缀和数组int []sums

2、由于前缀和数组sums[]里面存的是原数组num的前i项和，故使用其构造方法创建前缀数组sums[]时，要引入原数组num[]

3、注意创建sums[]数组时要注意，数组长度比数组要大一个数组空间，方便数组查询

4、创建完毕后，就直接根据传过来的right和left来对前缀和数组进行查找，注意查找right时注意加一，防止数组下标越界 ， 5、查找到之后，再让两个查找到的数进行相减

6、相减之后的数就返回其值

代码：(Java)

public class NumArray {public int[] sums;public NumArray(int[] nums) {sums = new int[nums.length + 1];sums[0] = 0;for(int i = 1; i <= nums.length ; i++) {sums[i] = sums[i - 1] + nums[i - 1];}}public int sumRange(int left, int right) {return sums[right+1] - sums[left];}}

public class Demo {public static void main(String[] args) {// TODO Auto-generated method stubint numbers [][] = {{-2, 0, 3, -5, 2, -1}, {0, 2}, {2, 5}, {0, 5}};int sums[] = new int[numbers.length - 1];NumArray numary  = new NumArray(numbers[0]);for(int i = 1; i < numbers.length; i++) {sums[i-1] = numary.sumRange(numbers[i][0], numbers[i][1]);System.out.print(sums[i - 1] + " ");}	}
}

复杂度分析：

• 时间复杂度：初始化 O(n)，每次检索 O(1)，其中 n 是数组 nums的长度。 初始化需要遍历数组 nums 计算前缀和，时间复杂度是 O(n)。 每次检索只需要得到两个下标处的前缀和，然后计算差值，时间复杂度是 O(1)。

• 空间复杂度：O(n)，其中 n 是数组 nums 的长度。需要创建一个长度为 n+1的前缀和数组。

注：仅供学习参考！

题目来源：力扣。