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

📖 文章摘要

本文详细解析LeetCode第303题“区域和检索 - 数组不可变”，这是一道考察前缀和的简单难度题目。文章提供了暴力求和和前缀和两种实现方案，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合学习前缀和和数组处理的读者。

核心知识点： 前缀和、数组处理、查询优化
难度等级： 简单
推荐人群： 具备基础算法知识，想要提升数组处理和查询优化能力的开发者

题目描述

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

计算索引 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 方法

解题思路

本题可以使用两种方法来实现：

暴力求和法：
- 每次查询时遍历区间求和
- 不需要额外空间
- 查询时间复杂度O(n)
- 适合查询次数少的情况
前缀和法：
- 预处理计算前缀和数组
- 利用前缀和快速计算区间和
- 查询时间复杂度O(1)
- 适合频繁查询的情况

图解思路

前缀和计算表

索引	原数组	前缀和	计算过程
0	-2	-2	-2
1	0	-2	-2 + 0
2	3	1	-2 + 0 + 3
3	-5	-4	1 + (-5)
4	2	-2	-4 + 2
5	-1	-3	-2 + (-1)

区间和查询步骤表

查询区间	计算方式	结果	时间复杂度
[0,2]	preSum[2] - preSum[-1]	1	O(1)
[2,5]	preSum[5] - preSum[1]	-1	O(1)
[0,5]	preSum[5] - preSum[-1]	-3	O(1)

代码实现

C# 实现

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

Python 实现

class NumArray:
    def __init__(self, nums: List[int]):
        self.preSum = [0] * (len(nums) + 1)
        for i in range(len(nums)):
            self.preSum[i + 1] = self.preSum[i] + nums[i]
    
    def sumRange(self, left: int, right: int) -> int:
        return self.preSum[right + 1] - self.preSum[left]

C++ 实现

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

执行结果

C# 实现

执行用时：124 ms
内存消耗：45.2 MB

Python 实现

执行用时：68 ms
内存消耗：17.8 MB

C++ 实现

执行用时：16 ms
内存消耗：17.1 MB

性能对比

语言	执行用时	内存消耗	特点
C#	124 ms	45.2 MB	实现简单，内存占用较大
Python	68 ms	17.8 MB	代码简洁，性能适中
C++	16 ms	17.1 MB	性能最优，内存占用小

代码亮点

🎯 使用前缀和优化查询效率
💡 巧妙处理边界情况
🔍 空间换时间的经典应用
🎨 代码结构清晰，易于维护

常见错误分析

🚫 前缀和数组大小错误
🚫 边界索引计算错误
🚫 未考虑空数组情况
🚫 查询范围验证不完整

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
暴力求和	O(n)	O(1)	空间占用小	查询慢
前缀和	O(1)	O(n)	查询快	需要额外空间

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第303题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

提示

解题思路

图解思路

前缀和计算表

区间和查询步骤表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流