【Leetcode 热题 100 - 扩展】303. 区域和检索 - 数组不可变
问题背景
给定一个整数数组 n u m s nums nums，处理以下类型的多个查询：
计算索引 l e f t left left 和 r i g h t right right（包含 l e f t left left 和 r i g h t right right）之间的 n u m s nums nums 元素的 和 ，其中 l e f t ≤ r i g h t left \le right left≤right。
实现 NumArray 类：
NumArray(int[] nums)使用数组 n u m s nums nums 初始化对象。int sumRange(int i, int j)返回数组 n u m s nums nums 中索引 l e f t left left 和 r i g h t right right 之间的元素的 总和 包含 l e f t left left 和 r i g h t right right 两点（也就是 n u m s [ l e f t ] + n u m s [ l e f t + 1 ] + . . . + n u m s [ r i g h t ] nums[left] + nums[left + 1] + ... + nums[right] nums[left]+nums[left+1]+...+nums[right])。
数据约束
● 1 ≤ n u m s . l e n g t h ≤ 1 0 4 1 \le nums.length \le 10 ^ 4 1≤nums.length≤104
● − 1 0 5 ≤ n u m s [ i ] ≤ 1 0 5 -10 ^ 5 \le nums[i] \le 10 ^ 5 −105≤nums[i]≤105
● 0 ≤ i ≤ j < n u m s . l e n g t h 0 \le i \le j < nums.length 0≤i≤j<nums.length
● 最多调用 1 0 4 10 ^ 4 104 次 s u m R a n g e sumRange sumRange 方法
解题过程
前缀和模板题，注意一下通常区间都是左闭右开的，定义的前缀和多预留一个位置来保存初始值零，这样能避免计算涉及到首位元素的时候需要特殊处理。
具体实现
class NumArray {private static int[] preSum;public NumArray(int[] nums) {int n = nums.length;preSum = new int[n + 1];for(int i = 0; i < n; i++) {// 实际的前缀和是从下标为 1 的位置开始记录的preSum[i + 1] = preSum[i] + nums[i];}}public int sumRange(int left, int right) {// 区间左闭右开，[left, right] 范围内的和需要用 (right + 1) 位置的元素来计算return preSum[right + 1] - preSum[left];}
}/*** Your NumArray object will be instantiated and called as such:* NumArray obj = new NumArray(nums);* int param_1 = obj.sumRange(left,right);*/