(Python3) - LeetCode (Medium) : 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

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

Find Two Non-overlapping Sub-arrays Each With Target Sum - LeetCode

two pointer로 해결한 문제였습니다. arr[i] >= 1이므로 오른쪽을 늘리면 합이 증가하고 왼쪽을 줄이면 합이 감소합니다. 따라서 합이 target을 초과했을 때 left를 이동시키는 sliding window를 사용할 수 있습니다.

📕 풀이방법

📔 입력 및 초기화

📑 현재 구간의 누적합 total과 left 각각 0,0으로 선언합니다.

📑 ans, best(arr[0:i] 범위에서 합이 target인 부분 배열의 최소 길이)를 적절히 큰 값으로 저장합니다.

📔 풀이과정

📑 arr의 원소를 순회하며 다음을 구합니다.
1. total에 현재 원소를 누적해 더해줍니다.

2. total이 target초과한 동안 left의 원소를 total에 제하며 증가시켜줍니다.

3. 현재 위치에서 새로운 target 구간을 찾지 못하더라도 이전까지의 최소 길이를 그대로 이어받습니다.

4. total == target인 경우

  4-1. 현 구간 길이 length를 선언해 값을 저장합니다.

  4-2. best[left] + length 값과 ans의 최솟값을 저장합니다. best[left]는 arr[0:left] 즉 index left-1까지만 포함하므로 현재 [left,right]과 겹치지 않습니다.

  4-3. best[right+1] 은 length의 최솟값과 비교해 저장합니다.

📑 시간 복잡도

O(n): right가 배열을 한 번 순회하고 left 역시 전체 실행에 대해 최대 n번만 이동하기 때문입니다.

📑 공간 복잡도

O(n): best 배열을 n+1크기로 사용하기 때문입니다.

📔 정답 출력 | 반환

ans가 INF라면 -1을 아니라면 ans를 반환합니다.

---

📕 Code

📔 Python3

class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        total,left = 0,0
        n = len(arr)
        INF = n + 1
        ans = INF
        best = [INF] * (n+1)
        for right,x in enumerate(arr):
            total += x
            while total > target:
                total -= arr[left]
                left+=1
            best[right+1] = best[right]
            if total == target:
                length = right - left + 1
                ans = min(ans, best[left] + length)
                best[right+1] = min(best[right+1], length)
        return -1 if ans == INF else ans

 

---

*더 나은 내용을 위한 지적, 조언은 언제나 환영합니다.