LeetCode #303: Range Sum Query -

Problem

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

题意

问题的输入为一个数组，含有一串数字。接着给出一个范围（[i, j]，注意是闭区间），要求算出a(i)+a(i+1)+···+a(j)的值（给定区间求和），以sumRange(i, j)的形式调用。
题目要求注意的是，第一，数组是不变的（其实我没太明白这一条是什么意思）；第二，sumRange函数会被调用很多次（应该是要求注意算法的时间复杂度）。
另外一点要注意的是，给出的代码结构如下：

class NumArray {
public:
    NumArray(vector<int> nums) {
        
    }
    
    int sumRange(int i, int j) {
        
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */

分析

这道题被放在动态规划的分类下面，实际属于一个比较简单的动态规划题。下面分析两种解法。

暴力算法

暴力算法下，不考虑对原来的给定的数组进行任何操作，在初始化时，直接声明一个新的vector<int> newNum，然后将nums的元素全都拷贝过去。
在调用sumRange时，按照最常规的解法，使用for(int index = i; index <= j; index++)遍历需要求和的区间 。
（代码略）

动态规划算法

对每一个问题进行分解，设int result = sumRange(i, j);，这个问题实际上可以分解成sumRange(0, j) - sumRange(0, i - 1)。因此，可以将所有sumRange(0, i)的结果都存储下来。
假设用一个新的数组sum来存储，则sum[i] = sumRange(0, i-1)（边界问题我们稍后处理）。
但是，我们别忘了动态规划的思想：根据当前的到的结果推出下一步的结果。sum[0] = nums[0]，sum[1] = nums[0]+nums[1] = sum[0] + num[1]···依次类推，可以得到sum[i] = sum[i - 1] + nums[i]。因此，在初始化时，我们只需要遍历一次nums数组，即可计算出所有位置的sum。

边界问题
按照以上得到的结果，应有sumRange(i, j) = sum[j] - sum[i - 1]。
这个问题有两种解决思路，一是在sumRange函数中添加判定语句，如果i==0则return sum[j]。优点是简单易懂；缺点是，增加了时间开销，每次调用sumRange函数都需要判断一次。
另外一种思路，在数组最前面加上一个0。这样一来，就有sumRange(i, j) = sum[j + 1] - sum[i]，避免了可能的越界。

Code

//Runtime: 169ms
class NumArray {
public:
    vector<int> sum;
    NumArray(vector<int> nums) {
        int tmp = 0;
        sum.push_back(tmp);
        int numSize = nums.size();
        for (int i = 0; i < numSize; i++){
            tmp += nums[i];
            sum.push_back(tmp);
        }

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

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * int param_1 = obj.sumRange(i,j);
 */