Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive. Example: Given nums = [-2, 0, 3, -5, 2, -1] sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3 Note:
给出一个整型数组 nums,寻找其中位置 i 与 j 之间元素的和,包括 i 与 j 元素。 例子: 给出 nums = [-2, 0, 3, -5, 2, -1] sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3 注意:
这道题其实不是考某种算法,而是考实现的方式。题目给出了一个初始化函数一个计算和的函数,如下:
public class NumArray {
public NumArray(int[] nums) {
}
public int sumRange(int i, int j) {
}
}
一般的实现方法很直接,定义一个变量 nums 数组,在初始化函数中赋值,在求和函数中直接遍历计算就行了很简单。但是如果直接这样做,答案会超时。题目明确指出求和函数会被多次调用,因此这里应该尽量简化求和函数,而把复杂度放在初始化时。
我们在初始化时,直接将每个元素的值改为从第一个元素到当前元素的和,这样在初始化时遍历计算一次。然后在求和时,只需要很简单地用两个位置的值相减就可以得出中间元素的和了。
public class NumArray {
int[] nums;
public NumArray(int[] nums) {
for (int i = 1; i < nums.length; i++)
nums[i] += nums[i-1];
this.nums = nums;
}
public int sumRange(int i, int j) {
if (i == 0) return nums[j];
else return nums[j] - nums[i-1];
}
}