問題：

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.

大意：

給出一個(gè)整型數(shù)組 nums，尋找其中位置 i 與 j 之間元素的和，包括 i 與 j 元素。
例子：

給出 nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
注意：

1. 你可以假設(shè)數(shù)組不會(huì)變。
2. 會(huì)多次調(diào)用 sumRange 函數(shù)。

思路：

這道題其實(shí)不是考某種算法，而是考實(shí)現(xiàn)的方式。題目給出了一個(gè)初始化函數(shù)一個(gè)計(jì)算和的函數(shù)，如下：

public class NumArray {
    
    public NumArray(int[] nums) {
        
    }

    public int sumRange(int i, int j) {
        
    }
}

一般的實(shí)現(xiàn)方法很直接，定義一個(gè)變量 nums 數(shù)組，在初始化函數(shù)中賦值，在求和函數(shù)中直接遍歷計(jì)算就行了很簡(jiǎn)單。但是如果直接這樣做，答案會(huì)超時(shí)。題目明確指出求和函數(shù)會(huì)被多次調(diào)用，因此這里應(yīng)該盡量簡(jiǎn)化求和函數(shù)，而把復(fù)雜度放在初始化時(shí)。

我們?cè)诔跏蓟瘯r(shí)，直接將每個(gè)元素的值改為從第一個(gè)元素到當(dāng)前元素的和，這樣在初始化時(shí)遍歷計(jì)算一次。然后在求和時(shí)，只需要很簡(jiǎn)單地用兩個(gè)位置的值相減就可以得出中間元素的和了。

代碼（Java）：

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

    public int sumRange(int i, int j) {
        if (i == 0) return nums[j];
        else return nums[j] - nums[i-1];
    }
}

合集：https://github.com/Cloudox/LeetCode-Record

查看作者首頁(yè)