Easy

题目描述

给定一个整数数组 nums，处理以下类型的多个查询:

计算数组 nums 在 left 和 right（包含 left 和 right）之间的元素的和，其中 left <= right。

实现 NumArray 类：

  • NumArray(int[] nums) 使用数组 nums 初始化对象。
  • int sumRange(int left, int right) 返回数组 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 (-2) + 0 + 3 = 1
numArray.sumRange(2, 5); // return 3 + (-5) + 2 + (-1) = -1
numArray.sumRange(0, 5); // return (-2) + 0 + 3 + (-5) + 2 + (-1) = -3

提示：

  • 1 <= nums.length <= 10^4
  • -10^5 <= nums[i] <= 10^5
  • 0 <= left <= right < nums.length
  • 最多调用 10^4 次 sumRange 方法

解题思路

这是一个经典的前缀和问题。题目要求多次查询区间和，如果每次查询都暴力计算，时间复杂度会很高。

解题思路：

  1. 暴力解法：每次查询都遍历从 left 到 right 的所有元素求和。虽然实现简单，但时间复杂度为 O(n)，当查询次数很多时效率低下。

  2. 前缀和解法（推荐）：预处理出前缀和数组，使得每次查询都能在 O(1) 时间内完成。

    • 前缀和数组 prefixSum[i] 表示从索引 0 到索引 i-1 的元素之和
    • 区间 [left, right] 的和 = prefixSum[right+1] - prefixSum[left]
    • 为了方便处理边界情况，我们让 prefixSum[0] = 0

前缀和的核心思想：

  • prefixSum[i] = nums[0] + nums[1] + ... + nums[i-1]
  • 区间和 nums[left] + ... + nums[right] = prefixSum[right+1] - prefixSum[left]

这种方法在构造函数中预处理前缀和数组，虽然初始化时间复杂度为 O(n)，但后续每次查询只需要 O(1) 时间，总体效率很高。

代码实现

class NumArray {
private:
    vector<int> prefixSum;
    
public:
    NumArray(vector<int>& nums) {
        int n = nums.size();
        prefixSum.resize(n + 1, 0);
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
    }
    
    int sumRange(int left, int right) {
        return prefixSum[right + 1] - prefixSum[left];
    }
};

class NumArray:
    def __init__(self, nums: List[int]):
        n = len(nums)
        self.prefix_sum = [0] * (n + 1)
        for i in range(n):
            self.prefix_sum[i + 1] = self.prefix_sum[i] + nums[i]

    def sumRange(self, left: int, right: int) -> int:
        return self.prefix_sum[right + 1] - self.prefix_sum[left]

public class NumArray {
    private int[] prefixSum;
    
    public NumArray(int[] nums) {
        int n = nums.Length;
        prefixSum = new int[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
    }
    
    public int SumRange(int left, int right) {
        return prefixSum[right + 1] - prefixSum[left];
    }
}

var NumArray = function(nums) {
    const n = nums.length;
    this.prefixSum = new Array(n + 1).fill(0);
    for (let i = 0; i < n; i++) {
        this.prefixSum[i + 1] = this.prefixSum[i] + nums[i];
    }
};

NumArray.prototype.sumRange = function(left, right) {
    return this.prefixSum[right + 1] - this.prefixSum[left];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
初始化O(n)O(n)
sumRangeO(1)O(1)

其中 n 是数组的长度。前缀和方法需要额外的 O(n) 空间来存储前缀和数组，但能够将查询时间复杂度降低到 O(1)，在多次查询的场景下具有明显优势。

相关题目