303. Range Sum Query - Immutable

Leetcode Dynamic Programming

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.

分析

这道题目还是非常直接的。难就难在题目说有大量的函数调用。既然是大量的函数调用，肯定需要把结果以某种形式预先存储起来。是直接存储结果吗？如果直接存储每个区间[$i,j$]之间的和，需要$O(n^2)$的空间和时间复杂度，当$n$大的时候肯定是不可取的。例如当$n=1000$时，大概需要4GB的存储，这样的算法不可能被实际应用。

一种比较好的思路是将前$i$个和存储起来，那么$i$到$j$之间的和，不就是两个和的差吗？基于这个思路空间复杂度降低为$O(n)$.

private int[] sum;

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

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