303. Range Sum Query - Immutable (Array, Design, Prefix Sum)

링크 - https://leetcode.com/problems/range-sum-query-immutable/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Easy

Intuition

subsums를 사용하면 쉽게 풀수있다. 캐시를 사용하는것이므로 sumRange()의 time complexity는 O(1)이다.

Code

class NumArray:

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

    def sumRange(self, left: int, right: int) -> int:
        return self.subsums[right+1] - self.subsums[left]
        


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(left,right)

Complexity

Time Complexity: O(n) - __init__, O(1) - sumRange()

Space Complexity: O(n)