刷算法(14)-区域和检索

303. 区域和检索 - 数组不可变

给定一个整数数组nums，求出数组从索引i到j(i ≤ j)范围内元素的总和，包含i,j两点。示例：

给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3

方法一：暴力

class NumArray {
    private int[] mData;

    public NumArray(int[] nums) {
        mData = nums;
    }
    
    public int sumRange(int i, int j) {
        int sum = 0;
        for (int k = i; k <= j; k++){
            sum  += mData[k];
        }
        return sum;
    }
}

方法二：把求和转化为作差

思路是先创造出来一个数组，该数组里第i个值表示i之前的原始数组nums之和，把问题转为新数组作差。

class NumArray {
    private int[] mData;

    public NumArray(int[] nums) {
        mData = new int[nums.length + 1];
        for (int i = 0;  i < nums.length; i++){
            mData[i+1] = mData[i] + nums[i]; 
        }
    }
    
    public int sumRange(int i, int j) {
        return mData[j+1] - mData[i];
    }
}