网站建设佰首选金手指三,事件营销名词解释,学做实体店网站,中国发展在线网站官网前缀和数组的应用 区域和检索 - 数组不可变题目描述前缀和数组代码演示 区域和检索 - 数组不可变 难度 - 简单 原题链接 - 区域和检索 - 数组不可变 题目描述 给定一个整数数组 nums#xff0c;处理以下类型的多个查询: 计算索引 left 和 right #xff08;包含 left 和 righ… 前缀和数组的应用 区域和检索 - 数组不可变题目描述前缀和数组代码演示 区域和检索 - 数组不可变 难度 - 简单 原题链接 - 区域和检索 - 数组不可变 题目描述 给定一个整数数组 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 1e4 -105 nums[i] 1e5 0 i j nums.length 最多调用 104 次 sumRange 方法 前缀和数组 核心思路是我们 new 一个新的数组 preSum 出来preSum[i] 记录 nums[0…i-1] 的累加和看图 10 3 5 2 看这个 preSum 数组如果我想求索引区间 [1, 4] 内的所有元素之和就可以通过 preSum[5] - preSum[1] 得出。 :这样sumRange 函数仅仅需要做一次减法运算避免了每次进行 for 循环调用最坏时间复杂度为常数 O(1)。 这个技巧在生活中运用也挺广泛的比方说你们班上有若干同学每个同学有一个期末考试的成绩满分 100 分那么请你实现一个 API输入任意一个分数段返回有多少同学的成绩在这个分数段内。 代码演示
class NumArray {private int[]preSum;public NumArray(int[] nums) {preSum new int[nums.length];preSum[0] nums[0];for(int i 1; i nums.length;i){preSum[i] preSum[i - 1] nums[i];}}public int sumRange(int left, int right) { return left ! 0 ? preSum[right] - preSum[left - 1] : preSum[right] ;}
}
