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

[暴力解法]：

时间分析：n

空间分析：n

［奇葩输出条件］：

［奇葩corner case］：

［思维问题］：

不知道怎么节约时间、空间

［一句话思路］：

先存成preflixsum，用做差法节约时间

［输入量］：空：正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：

［画图］：

［一刷］：

所有方法都要用的变量必须声明为成员变量，要仔细点别漏了

［二刷］：

［三刷］：

［四刷］：

［五刷］：

[五分钟肉眼debug的结果]：

［总结］：

先存成preflixsum，用做差法节约时间

［复杂度］：Time complexity: O(1) Space complexity: O(n)

［英文数据结构或算法，为什么不用别的数据结构或算法］：

this关键字调用属性或者方法，数组存完了之后更新一下

(1)this调用本类中的属性，也就是类中的成员变量；
 (2)this调用本类中的其他方法；

［关键模板化代码］：

省时间：

//store
int n = nums.length;
for (int i = 1; i < n; i++) {
            nums[i] += nums[i - 1];
        }

View Code

［其他解法］：

brute force

［Follow Up］：

［LC给出的题目变变变］：

307. Range Sum Query - Mutable 不是再加一次，而是换用线段树了。那我也没办法

304. Range Sum Query 2D - Immutable 二维就得要上dp了

[代码风格] ：

class NumArray {

int[] nums;

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

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

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

View Code

秒客网

303. Range Sum Query 范围求和系列

相关文章