Posted on | In

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

1
2
3
4
5
6
7
8
9
10
11
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class RangeSumQueryImmutable {
    private int[] sum;
    public RangeSumQueryImmutable/*NumArray*/(int[] nums) {
        sum = new int[nums.length + 1];
        for(int i=0;i< nums.length;i++){
            // 记录 0 - i 项的和 nums 0-2 的和 在 sum 下标 2+1 = 3 的位置
            sum[i+1] = sum[i] + nums[i];
        }
    }
    public int sumRange(int i, int j) {
        // num 第 0 - j 项 的和为 sum[j+1] 减去 i 之前的和，即 sum[i] 得到 sumRange(i,j)的和
        return sum[j+1] - sum[i];
    }
}