一、题目
给定一个整数数组 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
说明:
你可以假设数组不可变。
会多次调用 sumRange 方法。
https://leetcode-cn.com/problems/range-sum-query-immutable/
二、解题思路
整体思路
1、前缀和解法
用空间换时间，提前把结果计算好，存放在数组里，后面可以直接简单计算获取结果。
2、线段树（大材小用了，还是看307题）
关键问题
三、题解
暴力解法
每次查询用for循环把i到j加一遍
复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)
题解1: 前缀和
Java题解
class NumArray {
private int[] sum;
public NumArray(int[] nums) {
if (nums.length <= 0) {
return;
}
sum = new int[nums.length + 1];
// sum[0] = nums[0];
sum[0] = 0;
for (int i = 1; i < nums.length + 1; i++) {
// sum[i + 1] = sum[i] + nums[i];
sum[i] = sum[i - 1] + nums[i - 1];
}
}
public int sumRange(int i, int j) {
return sum[j + 1] - sum[i];
}
}
/**
* Your NumArray object will be instantiated and called as such:
* NumArray obj = new NumArray(nums);
* int param_1 = obj.sumRange(i,j);
*/
结果
image.png
复杂度分析
时间复杂度：O(1)，预先计算是O(n)
空间复杂度：O(n)
题解2: 用hashmap
学习用map存储一对数Pair
private Map<Pair<Integer, Integer>, Integer> map = new HashMap<>();
public NumArray(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
map.put(Pair.create(i, j), sum);
}
}
}
public int sumRange(int i, int j) {
return map.get(Pair.create(i, j));
}
四、测试数据
["NumArray","sumRange","sumRange","sumRange"]
[[[-2,0,3,-5,2,-1]],[0,2],[2,5],[0,5]]
参考
1、题解参考
2、优秀题解
https://leetcode-cn.com/problems/range-sum-query-immutable/solution/qu-yu-he-jian-suo-shu-zu-bu-ke-bian-by-leetcode/
