給一個整型數(shù)組，求sum(i, j)，包括i,j。

不帶腦子的辦法

這遍歷一遍不就行了。噌噌噌

public int sumRange(int i, int j) {
    int result = 0;
    for (int x = i; x <= j; x++) {
        result += nums[x];    // nums是給定的數(shù)組
    }
    
    return result;
}

完事，點擊提交，歡聲笑語打出GG。超時了，最后一個測試用例真的好長。。。

稍微動點腦子

每一次都要求一個和，那么在這個和的基礎(chǔ)上進行加減操作來求新的和。

public class NumArray {

    private int[] nums;
    private int lastStart, lastEnd, lastResult;
    private boolean first;
    
    public NumArray(int[] nums) {
        this.nums = nums;
        lastStart = 0;
        lastEnd = 0;
        lastResult = 0;
        first = true;
    }
    
    public int sumRange(int i, int j) {
        if (first) {
            int result = 0;
            for (int x = i; x <= j; x++) {
                result += nums[x];
            }
            lastStart = i;
            lastEnd = j;
            lastResult = result;
            first = false;
            return result;
        }
        int sum = lastResult;
        if (lastStart < i) {
            for (int x = lastStart; x < i; x++) {
                sum -= nums[x];
            }
        } else if (lastStart > i) {
            for (int x = i; x < lastStart; x++) {
                sum += nums[x];
            }
        }
        if (lastEnd < j) {
            for (int x = lastEnd + 1; x <= j; x++) {
                sum += nums[x];
            }
        } else if (lastEnd > j) {
            for (int x = j + 1; x <= lastEnd; x++) {
                sum -= nums[x];
            }
        }
        lastStart = i;
        lastEnd = j;
        lastResult = sum;
        return sum;
    }
}

就定義了一堆變量，還要對第一次進行判斷。不過好歹過了。

看完答案后的震驚

雖然說過了，但是想一想這個題有個dp的tag，這也沒用到dp啊，而且解法這么丑，肯定有很妙的解法。代碼看下面：

int[] nums;

public NumArray(int[] nums) {
    for(int i = 1; i < nums.length; i++)
        nums[i] += nums[i - 1];
        // 此時nums[i]存放的數(shù)據(jù)為0~i的和
    this.nums = nums;
}

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

真的，很震驚原來這樣就可以了。。這大概也是數(shù)學的奧妙吧。。還有就是個人思維太僵化了，不知道去轉(zhuǎn)化。