2145. Count the Hidden Sequences

https://leetcode.com/problems/count-the-hidden-sequences/description/?envType=daily-question&envId=2025-04-21

아 영어 너무 어렵다.

영어만 있는게 아니라 수학적 개념까지 있다.

해석해보면 prefix라는 list를 만드는데, 이 list는 prefix[i-1] 와 differenece[i]를 더하면 prefix[i]가 된다.

 

그렇게 해서 나온 prefix라는 list에서 최대값과 최소값이 생기겠지?

그렇다면 주어진 upper과 lower가 있는데, upper-max(prefix)를 lower-min(prefix) 뺀값에 1을 더하면 답이다.

(문제에서는 저 차로 만들 수 있는 list의 갯수를 구하라고했는데, list를 구해서 갯수를 세면 time-complexity나 space-complexity 모두 만족스럽지 못하여 그냥 값을 빼기만 하자.)

class Solution:
    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:
        prefix = []
        condition = []
        prefix.append(0)
        for i in range(len(differences)):
            prefix.append(prefix[i] + differences[i])
        max_offset, min_offset = max(prefix), min(prefix)

        left  = lower - min(prefix)
        right = upper - max(prefix)

        return max(0, right - left + 1)