題目描述
leetcode 第303題：區(qū)域和檢索 - 數(shù)組不可變
給定一個整數(shù)數(shù)組 nums，求出數(shù)組從索引 i 到 j（i ≤ j）范圍內(nèi)元素的總和，包含 i埃仪、j 兩點腾降。
實現(xiàn) NumArray 類：
NumArray(int[] nums) 使用數(shù)組 nums 初始化對象
int sumRange(int i, int j) 返回數(shù)組 nums 從索引 i 到 j（i ≤ j）范圍內(nèi)元素的總和，包含 i根盒、j 兩點（也就是 sum(nums[i], nums[i + 1], ... , nums[j])）
示例：
輸入：
["NumArray", "sumRange", "sumRange", "sumRange"]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
輸出：
[null, 1, -1, -3]
解釋：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1))
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
解題方法一
暴力法
原址題解
- 解題思路
每次遍歷數(shù)組nums箭启，累加從i到j(luò)之間的元素
- 復(fù)雜度
時間復(fù)雜度：O(n)
空間復(fù)雜度：O(1)
- 代碼實現(xiàn)
python3
class NumArray:
def __init__(self, nums: List[int]):
self.nums = nums
def sumRange(self, i: int, j: int) -> int:
sumN = 0
while i<=j:
sumN += self.nums[i]
i += 1
return sumN
php
class NumArray {
function __construct($nums) {
$this->nums = $nums;
}
function sumRange($i, $j) {
$sumN = 0;
while($i<=$j){
$sumN += $this->nums[$i];
$i++;
}
return $sumN;
}
}
解題方法二
前綴和
參照題解
- 解題思路
定義n獲取數(shù)組nums的長度
定義數(shù)組preSums越走，長度為n+1缓呛，元素值初始都為0
在[i,n)范圍內(nèi)遍歷nums催享，計算每一區(qū)間[i,j]內(nèi)元素的和并存入preSums
每次調(diào)用sumRange，preSums中j+1下標(biāo)的值與i下標(biāo)的值相減就是返回的總和
- 復(fù)雜度
時間復(fù)雜度：初始為O(n)哟绊，每次調(diào)用為O(1)
空間復(fù)雜度：O(n)
- 代碼實現(xiàn)
python3
class NumArray:
def __init__(self, nums: List[int]):
n = len(nums)
self.preSums = [0]*(n+1)
for i in range(n):
self.preSums[i+1] = self.preSums[i]+nums[i]
def sumRange(self, i: int, j: int) -> int:
return self.preSums[j+1]-self.preSums[i]
php
class NumArray {
function __construct($nums) {
$n = count($nums);
$this->preSums = [0];
for($i=0;$i<$n;$i++){
$this->preSums[$i+1] = $this->preSums[$i]+$nums[$i];
}
}
function sumRange($i, $j) {
return $this->preSums[$j+1]-$this->preSums[$i];
}
}
