Участник:Evgin/range sum query py

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/range-sum-query-immutable/

Python 3

Оптимальное решение на питоне (как бы я сделал):

class NumArray:
    def __init__(self, nums: List[int]):
        self.sums = [0] * (len(nums) + 1)
        for i in range(1, len(nums) + 1):
            self.sums[i] = self.sums[i - 1] + nums[i - 1]
 
    def sumRange(self, i: int, j: int) -> int:
        return self.sums[j + 1] - self.sums[i]


Переписанное на питон имеющееся решение:

(есть небольшое отличие в структуре хранимого массива)

class NumArray:
    def __init__(self, nums: List[int]):
        self.sums = [0] * len(nums)
        for i in range(len(nums)):
            if i == 0:
                self.sums[i] = nums[0]
            else:
                self.sums[i] = nums[i] + self.sums[i - 1]
 
    def sumRange(self, i: int, j: int) -> int:
        if i == 0:
            return self.sums[j]
        return self.sums[j] - self.sums[i - 1]

Но вообще говоря, у меня LeetCode отлично принял самое "наивное" решение:

(правда в 14 раз больше время, конечно)

class NumArray:
    def __init__(self, nums: List[int]):
        self.nums = nums
 
    def sumRange(self, i: int, j: int) -> int:
        return sum(self.nums[i:j + 1])