303. Range Sum Query - Immutable

題目

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 </pre> Note: You may assume that the array does not change. There are many calls to sumRange function.

翻譯

給一個int陣列，寫一個sumRange方法找尋陣列中元素i~j的總和。

範例： nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1 sumRange(2, 5) -> -1 sumRange(0, 5) -> -3

注意：你不能改變傳入陣列的值，然後sumRange會被忽叫很多次。

思路

1. 一開始的想法是sumRange被忽叫時就跑迴圈把i到j之間全部的值加起來，這很簡單，不過果然超時(TLE)了
2. 換個想法，sumRange會被忽叫很多次，因此在裡面寫迴圈不是一個好辦法
3. 這邊先用另外一個array來儲存a[0]~a[i]的加總，之後要取加總只要取array[j]-array[i-1]就可以
4. 以 [-2, 0, 3, -5, 2, -1] 為例，array = [-2,-2,1,-4,2,1]
5. sumRange(0, 2) --> i = 0，因此只要直接取array[j] = 2
6. sumRange(2, 5) --> 取array[5] = -1，array[1] = 0， sum = array[j]-array[i-1] = -1

解題

/**
 * @constructor
 * @param {number[]} nums
 */
var NumArray = function(nums) {
    var sum = 0;
    this.array = [];
    // 先將加總存到一個array
    for(var i in nums){
        sum += nums[i];
        this.array.push(sum);
    }
};

/**
 * @param {number} i
 * @param {number} j
 * @return {number}
 */
NumArray.prototype.sumRange = function(i, j) {
    if(i == 0){
        return this.array[j];
    }
    //取出的時候，只要取array[0]到array[j]的加總sumJ 減去 array[0]到array[i]的加總，就是i到j的加總
    return this.array[j] - this.array[i-1];
};


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