Skip to main content

303. Range Sum Query - Immutable

分析


题解

暴力版本

class NumArray {
nums: number[]

constructor(nums: number[]) {
this.nums = nums
}

// [left, right]
sumRange(left: number, right: number): number {
let sum = 0
for (let i = left; i <= right && i < this.nums.length; i++) {
sum += this.nums[i]
}
return sum
}
}

前缀版本

class NumArray {
// prefix[i] 表示 nums[0] + ... + nums[i] 的值
prefix: number[]

constructor(nums: number[]) {
const temp = []
temp[-1] = 0
for (let i = 0; i < nums.length; i++) {
temp[i] = temp[i - 1] + nums[i]
}
this.prefix = temp
}

// [left, right]
sumRange(left: number, right: number): number {
return this.prefix[right] - this.prefix[left - 1]
}
}