Leetcode-303-区域和检索

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

题目描述

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

示例：

给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

说明:

你可以假设数组不可变。
会多次调用 sumRange 方法。

思路 ： 前缀和

• 一上来我们不说前缀和这个思路，先说个普通的暴力解法

暴力解法

• 每次调用 sumrange 时，我们都使用for循环将索引 i 到 j 之间的每个元素相加。

private int[] data;

public NumArray(int[] nums) {
    data = nums;
}

public int sumRange(int i, int j) {
    int sum = 0;
    for (int k = i; k <= j; k++) {
        sum += data[k];
    }
    return sum;
}

复杂度分析

• 时间复杂度：每次查询的时间 O(n)，每个 sumrange 查询需要 O(n)时间。
• 空间复杂度：O(1)，请注意，data 是对 nums 的引用，不是它的副本。

前缀和

• 假设我们预先计算了从数字 0 到 k的累积和。我们可以用这个信息得出 sum(i，j)吗？
• 让我们将 sum[k] 定义为nums[0⋯k−1] 的累积和（包括这两个值）：

• 现在，我们可以计算 sumrange如下：

private int[] sum;

public NumArray(int[] nums) {
    // sum[0] = 0
    // sum[] 数组用于计算前缀和
    sum = new int[nums.length + 1];
    for (int i = 0; i < nums.length; i++) {
        sum[i + 1] = sum[i] + nums[i];
    }
}

public int sumRange(int i, int j) {
    // 计算索引下标区间内的求和公式
    return sum[j + 1] - sum[i];
}

注意：

• 注意，在上面的代码中，我们插入了一个虚拟 0 作为 sum 数组中的第一个元素。这个技巧可以避免在 sumrange 函数中进行额外的条件检查。

复杂度分析

• 时间复杂度：每次查询的时间 O(1)，

  • O(N)预计算时间。由于累积和被缓存，每个sumrange都可以用 O(1)时间计算。

• 空间复杂度：O(n).

打赏