区域和检索-数组不可变-LeetCode

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

🎯 问题描述

描述：
给定一个整数数组 nums，处理以下类型的多个查询：
计算索引 left 和 right（包含 left 和 right）之间的 nums 元素的和。

实现 NumArray 类：

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

说明：

• 这是一个前缀和的基础应用题。

• 核心策略：

  • 利用数学性质：区间和 $[left, right]$ 等于前缀和 $[0, right]$ 减去前缀和 $[0, left-1]$。
  • 公式：$Sum(left, right) = \sum_{i=0}^{right} nums[i] - \sum_{i=0}^{left-1} nums[i]$。

• 代码特点：

  • 当前代码在 sumRange 中直接使用了 Python 的切片和内置 sum 函数。这是一种写法简洁但效率较低的“伪前缀和”实现。

• 示例：

• 示例 1：

输入：
["NumArray", "sumRange", "sumRange", "sumRange"]
, [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))

💻 解题思路

思路1：朴素前缀和（当前代码实现）

核心逻辑

1. 存储原数组：
   • 在 __init__ 中保存传入的 nums。
2. 利用切片计算：
   • sum(self.nums[:right+1])：计算从下标 0 到 right 的累加和。
   • sum(self.nums[:left])：计算从下标 0 到 left-1 的累加和。
   • 两者相减即为区间 [left, right] 的和。

代码实现

class NumArray:

    def __init__(self, nums: List[int]):
        self.nums = nums

    def sumRange(self, left: int, right: int) -> int:
        # 计算 [0, right] 的和
        sum_right = sum(self.nums[:right+1])
        # 计算 [0, left-1] 的和
        sum_left = sum(self.nums[:left])
        
        return sum_right - sum_left

📊 性能分析

• 时间复杂度：
  • __init__: $O(1)$。
  • sumRange: $O(N)$。
    • 因为每次调用 sum 和切片操作都需要遍历数组的一部分。如果有 $Q$ 次查询，总时间复杂度为 $O(Q \cdot N)$。
    • 注：这在查询次数较多时效率较低。
• 空间复杂度：$O(1)$（不计输入存储）。

💡 优化思路：标准前缀和（推荐）

如果题目中 sumRange 被频繁调用，我们应该在初始化时预处理前缀和数组，将查询复杂度降为 $O(1)$。

优化代码

class NumArray:
    def __init__(self, nums: List[int]):
        # 构建前缀和数组 pre_sum
        # pre_sum[i] 表示 nums[0...i-1] 的和
        # 长度为 n+1，pre_sum[0] = 0
        self.pre_sum = [0]
        for num in nums:
            self.pre_sum.append(self.pre_sum[-1] + num)

    def sumRange(self, left: int, right: int) -> int:
        # 区间 [left, right] 的和 = pre_sum[right+1] - pre_sum[left]
        return self.pre_sum[right + 1] - self.pre_sum[left]

优化后性能

• 时间复杂度：
  • __init__: $O(N)$（预处理）。
  • sumRange: $O(1)$（直接查表）。
• 空间复杂度：$O(N)$（存储前缀和数组）。

思考

1. 为什么当前代码能工作？

   • 它利用了前缀和的数学定义 $S_{i,j} = S_{0,j} - S_{0,i-1}$。
   • Python 的 sum() 函数和切片语法 [:k] 非常强大，掩盖了底层的遍历过程。

2. 当前代码的隐患：

   • 如果 nums 长度很大（例如 $10^5$），且 sumRange 被调用 $10^5$ 次，总运算次数将达到 $10^{10}$，会导致超时。
   • 面试中通常期望看到“预处理 + $O(1)$ 查询”的标准前缀和解法。

3. 边界处理：

   • 当 left = 0 时，self.nums[:0] 是空列表，sum 为 0，逻辑正确。