303-Range Sum Query - Immutable

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);
    }
}