0%

刷算法(14)-区域和检索

303. 区域和检索 - 数组不可变

给定一个整数数组nums,求出数组从索引i到j(i ≤ j)范围内元素的总和,包含i,j两点。示例:

1
2
3
4
给定 nums = [-2, 0, 3, -5, 2, -1],求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

方法一:暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class NumArray {
private int[] mData;

public NumArray(int[] nums) {
mData = nums;
}

public int sumRange(int i, int j) {
int sum = 0;
for (int k = i; k <= j; k++){
sum += mData[k];
}
return sum;
}
}

方法二:把求和转化为作差

思路是先创造出来一个数组,该数组里第i个值表示i之前的原始数组nums之和,把问题转为新数组作差。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class NumArray {
private int[] mData;

public NumArray(int[] nums) {
mData = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++){
mData[i+1] = mData[i] + nums[i];
}
}

public int sumRange(int i, int j) {
return mData[j+1] - mData[i];
}
}