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

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

题目描述

• 给定一个整数数组 nums，求出数组从索引 i 到 j（i ≤ j）范围内元素的总和，包含 i、j两点。

• 实现 NumArray 类：

  • NumArray(int[] nums) 使用数组 nums 初始化对象

  • int sumRange(int i, int j)返回数组nums从索引i到 j（i ≤ j）范围内元素的总和，包含i、j两点（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）

示例 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))

• 提示：

  • 0 <= nums.length <= 10^4

  • -10^5 <= nums[i] <= 10^5

  • 0 <= i <= j < nums.length

  • 最多调用10^4 次 sumRange 方法

算法思路：前缀和

• 关于区间求和，常用手段是前缀和。（如果学过GRE数学，那么可以将前缀和和百分位数（percentile）的定义放在一起）

• 我们举一个简单的例子：

  • 假如需要对nums = [1, 2, 3, 4, 5]进行处理，我们先得到前缀和。所谓前缀和就是从数组的0位置开始到当前位置的和值，比如nums的前缀和是preSum = [0, 1, 1 + 2, 1 + 2 + 3, 1 + 2 + 3 + 4, 1 + 2 + 3 + 4 + 5]，即preSum = [0, 1, 3, 6, 10, 15](preSum[0] = 0 可以认为是初始化)；
  • 得到前缀和之后，可以求区间的和值。比如说求 [2 , 4] 区间的和值，那么就是3 + 4 + 5 = preSum[4 + 1] - preSum[2] = 15 - 3 = 12。

class NumArray {
    private int[] sum;

    // 1.提前计算出前缀和
    public NumArray(int[] nums) {
        sum = new int[nums.length + 1];
        for(int i = 0; i < nums.length;i++){
            sum[i + 1] = sum[i] + nums[i];
        }
    }
    
    // 2. 计算出这段数组的和
    public int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */

复杂度分析

• 时间复杂度 ：O(n) , 其中n是原数组的长度，原因是要遍历encoded数组一次
• 空间复杂度 ：O(1)

打赏