力扣数组
区间和（卡码网0058）
区间和（卡码网0058）
https://kamacoder.com/problempage.php?pid=0058
题目
给定一个整数数组 nums 和多个查询区间 [l, r]，对于每个查询，计算 nums 中从索引 l 到索引 r 的元素之和。
示例
输入：
nums = [1, 2, 3, 4, 5]
queries = [[0, 2], [1, 3], [2, 4]]
输出：
[6, 9, 12]
解释：
[0,2] → 1+2+3 = 6
[1,3] → 2+3+4 = 9
[2,4] → 3+4+5 = 12约束
- 数组长度 n ≤ 10^5
- 查询次数 q ≤ 10^5
- 元素值为整数
思路
暴力解法每次查询都遍历区间求和，时间复杂度 O(n·q)，在 n 和 q 都达到 10^5 时会超时。
前缀和优化：
- 预处理一个前缀和数组
prefix，其中prefix[i]表示nums[0] + nums[1] + ... + nums[i]，即前 i+1 个元素的和 - 前缀和递推公式：
prefix[0] = nums[0]，prefix[i] = prefix[i-1] + nums[i] - 对于任意查询
[l, r]，区间和 =prefix[r] - prefix[l-1]（当 l > 0 时）；若 l == 0，区间和 =prefix[r] - 统一写法：区间和 =
prefix[r] - prefix[l-1]，其中prefix[-1]视为 0
预处理 O(n)，每次查询 O(1)，总复杂度 O(n + q)。
解法
class Solution:
def rangeSum(self, nums: list[int], queries: list[list[int]]) -> list[int]:
# 1. 构建前缀和数组
n = len(nums)
prefix = [0] * n
prefix[0] = nums[0]
for i in range(1, n):
prefix[i] = prefix[i - 1] + nums[i]
# 2. 处理每个查询
result = []
for l, r in queries:
if l == 0:
result.append(prefix[r])
else:
result.append(prefix[r] - prefix[l - 1])
return result
# 示例调用
if __name__ == "__main__":
sol = Solution()
print(sol.rangeSum([1, 2, 3, 4, 5], [[0, 2], [1, 3], [2, 4]]))
# 输出: [6, 9, 12]解释
| 代码片段 | 作用与原因 |
|---|---|
prefix = [0] * n | 创建与前缀和等长的数组，prefix[i] 表示 nums[0] 到 nums[i] 的和 |
prefix[0] = nums[0] | 初始化前缀和第一个元素 |
prefix[i] = prefix[i-1] + nums[i] | 递推公式：当前前缀和 = 前一个前缀和 + 当前元素值 |
if l == 0: result.append(prefix[r]) | 当左边界为 0，区间和直接取 prefix[r] |
result.append(prefix[r] - prefix[l-1]) | l > 0 时，区间和 = 右边界前缀和 - 左边界前一位置前缀和 |
prefix[r] - prefix[l-1] | 核心公式：子数组和 = 两个前缀和的差值 |