给定一个整数数组nums,求出数组从索引i 到j (i≤j) 范围内元素的总和,包含i, j 两点。给定 nums = [-2, 0, 3, -5, 2, -1],求和函数为 sumRange(),
sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3
最简单的当然是每次都遍历,复杂度高。
其次可以用动态规划来做,dp[i]表示 [0,i] 范围内的数字之和,所以[i,j]范围内的数字之和就可以表示为dp[j] - dp[i-1]。注意当i为0时,直接返回dp[j]。