303. Range Sum Query Immutable - jiejackyzhang/leetcode-note GitHub Wiki

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:

You may assume that the array does not change.

There are many calls to sumRange function.

Array类题目。

由于数组不变，而sumRange又会多次被调用，每次调用时再计算显然浪费时间。 因此可以考虑在初始化时就将计算结果存下来。

若采用(i,j)->sum这样的结构保存结果，则初始化时所用时间为O(n^2)，占用空间O(n^2)，显然效率不高，而且占用内存过多。

若令sum[j] = nums[0] + ... + nums[j-1]，则sumRange(i,j) = sum[j+1] - sum[i]。 这样只需一个长度为nums.length+1的数组来保存求和结果。

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

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


// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.sumRange(1, 2);