有勇气的牛排博客
☰

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

有勇气的牛排 30 算法 2025-08-09 22:17:41
进群口令：博客

题目

标签：设计、数组、前缀和

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

  1. 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right

实现 NumArray 类：

  • NumArray(int[] nums) 使用数组 nums 初始化对象
  • int sumRange(int i, int j) 返回数组 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 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 <= nums.length <= 104
  • -105 <= nums[i] <= 105
  • 0 <= i <= j < nums.length
  • 最多调用 104 次 sumRange 方法

前缀和 方法

思路

  1. 先计算前缀和数组 prefix_num，其中：

    prefix[k]=nums[0]+nums[1]+...+nums[k−1]prefix[k]=nums[0]+nums[1]+...+nums[k-1]

    注意：prefix_sum[0]=[0]

  2. 区间 [i, j] 的和可以通过公式快速得到：

    sumRange(i,j)=prefixsum[j+1]−prefixsim[i]sumRange(i, j) = prefix_sum[j+1]-prefix_sim[i]

案例

nums = [-2, 0, 3, -5, 2, -1]
prefix_sum = [0, -2, -2, 1, -4, -2, -3]

题目：
  sumRange(2, 5)
= prefix_sum[6] - prefix_sum[2]
= (-3)-(-2)
= -1

时间复杂度：

  • 初始化：O(n)
  • 每次查询：O(1)

空间复杂度：O(n)

python实现

# -*- coding: utf-8 -*-
class NumArray:
    def __init__(self, nums):
        # 构造前缀和数组
        self.prefix_sum = [0]
        for num in nums:
            self.prefix_sum.append(self.prefix_sum[-1] + num)

    def sumRange(self, i, j):
        # 区间和 = 前缀和差
        return self.prefix_sum[j+1]-self.prefix_sum[i]


numArray = NumArray([-2, 0, 3, -5, 2, -1])
print(numArray.sumRange(0, 2))  # 1
print(numArray.sumRange(2, 5))  # -1
print(numArray.sumRange(0, 5))  # -3

评论区

×
×