303. Range Sum Query - Immutable (Easy)

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:

1. You may assume that the array does not change.
2. There are many calls to sumRange function.

Solution 1: DP

Use an array to record preSum of input array. sums[i] means the sum of first i elements.
Then the range sum can be gotten by the sum of first j elements minus the sum of first i-1 elements.

    int[] sums;

    public NumArray(int[] nums) { //O(n); O(n) pre-computation
        if (nums.length == 0) {
            return;
        }

        sums = new int[nums.length];
        sums[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            sums[i] = sums[i - 1] + nums[i];
        }
    }

    public int sumRange(int i, int j) { //O(1); O(1)
        return i == 0 ? sums[j] : sums[j] - sums[i - 1];
    }

Solution 2: DP

dp数组多加一位，省去边界条件判断。

    private int[] sum;

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

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