力扣小白刷题之303题区域和检索 - 数组和不变

题目描述

给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包括 i， j 两点。
说明：

1. 假设数组不可变
2. 会多次调用sumRange方法

思路

说明中提到：会多次调用sumRange方法，所以每次都逐个相加计算子区间的和不是理想的做法，可以借助缓存来保存区域和。
若使用二维数组dp，dp[i][j]表示 i 到 j 的区域和，需要 O(n^2)空间复杂度。

考虑以上因素，我们使用一维sum，其中sum[i]表示 0 到 i - 1索引处的累加和，即sum[i] 存储 nums前 i 个元素的和。则易得到 i 到 j 的区域和公式：sum[j + 1] - sums[i]

缓存+动态规划

1. 定义sum数组，长度为 n + 1。sum[k] 为 nums[0 … k - 1]的累加和，
2. 遍历数组，保存累加和,遍历区间[1, n ]：sum[i] = sum[i - 1] + nums[i - 1]
3. 索引i 到 j 间的区域和公式：sum[j + 1] - sum[i]

复杂度分析：
时间复杂度： O(n)，每次查询只需要O(1).，由于累积和被缓存，每个sumRange查询都可以用O(1)时间计算。
空间复杂度： O(n)

代码

问题

1. 前缀和：一个数组的某项下标之前(包括此项元素)的所有数组元素的和。
   本题中，sum[i] 表示第 i 个元素(下标为 i - 1)结尾的元素的前缀和。sum[i] = dp[i - 1] + nums[i - 1]
2. 遍历区间 从 1 开始 (i = 1)