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
求一个数组随机长度的和， 注意是sumRange被频繁调用：
当时想都没想写出来的代码是这样的， 频繁调用就是用缓存嘛...= =
这个典型的懒人思维，这样的缓存命中率其实相当低的，费时还费空间。
自然提交也 Time Limit Exceeded
最近的确忙，也没时间刷题。 稍微难点的自己也不想研究了...win10真不是用来写程序的 好麻烦真是！！
public class NumArray {
private final int[] nums;
private int len = 0;
private final Map<String,Integer> cache = new HashMap<>();
public NumArray(int[] nums) {
this.nums = nums;
len = nums.length;
}
public int sumRange(int i, int j) {
if(j > len){
j = len;
}
String key = i + "_" + j; //非常笨的缓存...
if(cache.containsKey(key)) return cache.get(key);
int sum = 0;
for(int k=i; k<=j;k++){
sum += nums[k];
}
cache.put(key,sum);
return sum;
}
}
正确的答案是：
在初始化数组的时候执行一次累加，每次求和就只需要 j位减去 i位之前的和就行了
public class NumArray {
private final int[] nums;
private final int[] sums;
private int len = 0;
public NumArray(int[] nums) {
this.nums = nums;
len = nums.length;
sums = new int[len];
int s = 0;
for(int k=0; k<len; k++){
s+=nums[k];
sums[k] = s;
}
}
public int sumRange(int i, int j) {
if(j > len){
j = len - 1;
}
return sums[j] - (i!=0 ? sums[i-1] : 0);
}
}
