LeetCode303_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 方法

二、题解

方法一：标准前缀和问题

class NumArray {int[] sums;//定义前面n项的和public NumArray(int[] nums) {sums = new int[nums.length + 1];//多初始化一位，方便后续计算for (int i = 0; i < nums.length; i++) {sums[i + 1] = sums[i] + nums[i];}}public int sumRange(int left, int right) {return sums[right + 1] - sums[left];}
}/*** Your NumArray object will be instantiated and called as such:* NumArray obj = new NumArray(nums);* int param_1 = obj.sumRange(left,right);*/

LeetCode 234. 回文链表
LeetCode 237. 删除链表中的节点
LeetCode 242. 有效的字母异位词
LeetCode 257. 二叉树的所有路径
LeetCode 258. 各位相加
LeetCode 263. 丑数
LeetCode 268. 丢失的数字
LeetCode 283. 移动零
LeetCode 287. 寻找重复数
LeetCode 290. 单词规律
LeetCode 292. Nim 游戏
LeetCode 303. 区域和检索 - 数组不可变

声明：
        题目版权为原作者所有。文章中代码及相关语句为自己根据相应理解编写，文章中出现的相关图片为自己实践中的截图和相关技术对应的图片，若有相关异议，请联系删除。感谢。转载请注明出处，感谢。

By luoyepiaoxue2014

B站： https://space.bilibili.com/1523287361 点击打开链接
微博： http://weibo.com/luoyepiaoxue2014 点击打开链接