1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

Обновлено: 2024-03-12
1 мин
[]

Содержание

LeetCode problem 1477

class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        d = {0: 0}
        s, n = 0, len(arr)
        f = [inf] * (n + 1)
        res = inf
        for i, v in enumerate(arr, 1):
            s += v
            f[i] = f[i - 1]
            if s - target in d:
                j = d[s - target]
                f[i] = min(f[i], i - j)
                res = min(res, f[j] + i - j)
            d[s] = i
        return -1 if res > n else res