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

一、 问题描述

给定一个整数数组 nums，处理以下类型的查询: 计算索引 left 和 right 之间的元素和（包括 left 和 right），其中 left <= right

实现 NumArray 类：

• NumArray(int[] nums) 使用数组 nums 初始化对象
• int sumRange(int left, int right) 返回数组 nums 中索引 left 和 right 之间的元素和（包含 left 和 right）

二、 方案一：暴力法

1、思路

对于每次查询，直接遍历 left 和 right 之间的所有元素，计算它们的和。

2、代码实现

type NumArray struct {
    nums []int
}
func Constructor(nums []int) NumArray {
    return NumArray{nums: nums}
}
func (this *NumArray) SumRange(left int, right int) int {
    sum := 0
    for i := left; i <= right; i++ {
        sum += this.nums[i]
    }
    return sum
}

3、复杂度分析

• 时间复杂度：初始化为 O(1)，每次查询为 O(n)，其中 n 是数组 nums 的长度。
• 空间复杂度：O(1)。

三、方案二：前缀和数组

1、思路

创建一个前缀和数组，其中第 i 个元素表示原数组 nums 中前 i 个元素的和。这样，查询 left 和 right 之间的元素和就可以通过计算 prefixSum[right] - prefixSum[left-1] 来得到。

2、代码实现

type NumArray struct {
    prefixSum []int
}
func Constructor(nums []int) NumArray {
    prefixSum := make([]int, len(nums)+1)
    // prefixSum[i] 表示前 i-1个元素的累加和
    for i := 1; i <= len(nums); i++ {
        prefixSum[i] = prefixSum[i-1] + nums[i-1]
    }
    return NumArray{prefixSum: prefixSum}
}
func (this *NumArray) SumRange(left int, right int) int {
    return this.prefixSum[right+1] - this.prefixSum[left]
}

3、复杂度分析

• 时间复杂度：初始化为 O(n)，每次查询为 O(1)，其中 n 是数组 nums 的长度。
• 空间复杂度：O(n)，用于存储前缀和数组。

四、总结

方案	初始化时间	查询时间	空间复杂度
暴力法	O(1)	O(n)	O(1)
前缀和数组	O(n)	O(1)	O(n)

前缀和数组在初始化时需要额外的时间来构建前缀和数组，但在查询时具有常数时间复杂度，适合于频繁查询的场景。而暴力法在查询时需要线性时间，适合于查询次数较少的场景。