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

[zeikar]

Problem Link

https://leetcode.com/problems/find-two-non-overlapping-sub-arrays-each-with-target-sum/

Problem Summary

합이 target인 겹치지 않는 부분 배열 두 개를 골라서 길이의 합을 최소로 만드는 문제.

Solution

일단 arr[i] >= 1이라 전부 양수다. 그래서 합이 target인 구간은 슬라이딩 윈도우로 죽 밀면서 찾아주면 된다.

겹치지 않게 두 개를 고르는 게 문제인데, 오른쪽 구간을 고정하면 왼쪽은 제일 짧은 것 하나만 알면 된다. minLen[i]를 i 이하에서 끝나는 유효 구간의 최소 길이로 두면, i가 커질 때 후보가 추가만 되니까 이 값은 커질 수가 없다. 커질 수도 있나 했는데 아니었다. 그래서 이분탐색이나 구간 최소 자료구조 없이 그냥 밀면서 갱신해주면 된다.

스캔은 두 번 했는데 에디토리얼은 한 번으로 끝낸다... l <= r이라 윈도우를 찾은 시점에 best[l]이 이미 계산되어 있어서, 갱신이랑 조합을 같은 루프에서 해주면 된다.

시간복잡도는 O(n).

Source Code

class Solution:
    def minSumOfLengths(self, arr: list[int], target: int) -> int:
        n = len(arr)
        arr.append(987654321)
        minLen = [987654321 for _ in range(n)]

        l, r = 0, 0
        s = 0
        while l <= r:
            if l == n:
                break
            
            if s < target:
                if r > 1:
                    minLen[r-1] = min(minLen[r-1], minLen[r-2])
                s += arr[r]
                r += 1
            elif s == target:
                if r > 1:
                    minLen[r-1] = min(minLen[r-1], minLen[r-2])
                minLen[r-1] = min(minLen[r-1], r - l)
                s += arr[r]
                r += 1
            else:
                s -= arr[l]
                l += 1
        
        ans = 987654321
        l, r = 0, 0
        s = 0
        while l <= r:
            if l == n:
                break
            
            if s < target:
                s += arr[r]
                r += 1
            elif s == target:
                if l > 0:
                    ans = min(ans, minLen[l-1] + r - l)
                s += arr[r]
                r += 1
            else:
                s -= arr[l]
                l += 1

        return ans if ans != 987654321 else -1