Участник:Timplech/count-of-range-sum

Материал из DISCOPAL
< Участник:Timplech
Версия от 17:40, 28 декабря 2020; Timplech (обсуждение | вклад) (Новая страница: «https://leetcode.com/problems/count-of-range-sum Python3 <code-python> class Solution: def countRangeSum(self, nums: List[int], lower: int, upper: int) -> i…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

https://leetcode.com/problems/count-of-range-sum

Python3

class Solution:
    def countRangeSum(self, nums: List[int], lower: int, upper: int) -> int:
        sums = [0 for _ in range(len(nums) + 1)]
        for i in range(len(nums)):
            sums[i + 1] = sums[i] + nums[i]
        return Solution.countAndMergeSort(sums, 0, len(sums), lower, upper)
    def countAndMergeSort(sums, start, end, lower, upper):
            if end - start <= 1:
                return 0
            mid = start + (end - start) // 2
            count = Solution.countAndMergeSort(sums, start, mid, lower, upper) + \
                    Solution.countAndMergeSort(sums, mid, end, lower, upper)
            j, k, r = mid, mid, mid
            tmp = []
            for i in range(start, mid):
                while k < end and sums[k] - sums[i] < lower:
                    k += 1
                while j < end and sums[j] - sums[i] <= upper:
                    j += 1
                count += j - k
 
                while r < end and sums[r] < sums[i]:
                    tmp.append(sums[r])
                    r += 1
                tmp.append(sums[i])
            sums[start:start+len(tmp)] = tmp
            return count