LeetCode 筆記 - 303. Range Sum Query - Immutable

Posted on

題目在此 303. Range Sum Query - Immutable

給定一個數列，請根據給定的範圍計算出區段總和

解題思維

這題我們要用 Prefix Sum 來幫助我們

基本概念很簡單，先建立起 Prefix Sum Table
每個 i 代表的是從 matrix[0] 到 matrix[i] 的區段總和

如此一來，任意 i, j 的區段總和就變成是

prefix_sum_table[j] - prefix_sum_table[i - 1]

完成 🥰

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class NumArray:

    def __init__(self, nums: List[int]):
        self.nums = nums
        
        self.sum_table = [0] * len(nums)
        
        temp = 0
        for i in range(len(nums)):
            temp += nums[i]
            
            self.sum_table[i] = temp

    def sumRange(self, i: int, j: int) -> int:
        
        if i == j:
            return self.nums[i]
        
        if i == 0:
            return self.sum_table[j]
        return self.sum_table[j] - self.sum_table[i - 1]

相關文章