网站咋开通,python3网站开发,国际购物网站排名,华为中小企业解决方案303. 区域和检索 - 数组不可变
给定一个整数数组 nums#xff0c;处理以下类型的多个查询:
计算索引 left 和 right #xff08;包含 left 和 right#xff09;之间的 nums 元素的 和 #xff0c;其中 left right 实现 NumArray 类#xff1a;
NumArray(int[] num…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))提示
1nums.length1041 nums.length 10^41nums.length104−105nums[i]105-10^5 nums[i] 10^5−105nums[i]1050ijnums.length0 i j nums.length0ijnums.length最多调用 10410^4104 次 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[right1] - 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 的长度。需要创建一个长度为 n1的前缀和数组。
注仅供学习参考
题目来源力扣。
