arr and an integer target.
You have to find two non-overlapping sub-arrays of arr each with a sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.
Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.
Example 1:
Input: arr = [3,2,2,4,3], target = 3 Output: 2 Explanation: Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2.
Example 2:
Input: arr = [7,3,4,7], target = 7 Output: 2 Explanation: Although we have three non-overlapping sub-arrays of sum = 7 ([7], [3,4] and [7]), but we will choose the first and third sub-arrays as the sum of their lengths is 2.
Example 3:
Input: arr = [4,3,2,6,2,3,4], target = 6 Output: -1 Explanation: We have only one sub-array of sum = 6.
Constraints:
1 <= arr.length <= 1051 <= arr[i] <= 10001 <= target <= 108배열, 해시 테이블, 이분 탐색, 동적 계획법, 슬라이딩 윈도우
주어진 정수 배열 arr과 목표 합 target이 있을 때, 합이 target이 되는 **서로 겹치지 않는 두 개의 부분 배열(subarray)**을 찾아야 합니다. 가능한 쌍이 여러 개라면, 두 부분 배열의 길이 합이 최소가 되는 경우를 찾아 그 길이 합을 반환합니다. 만약 그러한 두 부분 배열을 찾을 수 없다면 -1을 반환합니다.
arr (길이 1 ~ 100,000), 정수 target (1 ~ 10^8)이 문제는 **슬라이딩 윈도우(Sliding Window)**와 **동적 계획법(Dynamic Programming)**을 결합하여 해결합니다.
arr[i] >= 1), 두 포인터(left, right)를 이용해 합이 target인 부분 배열을 O(N)에 모두 찾을 수 있습니다.dp[i]를 인덱스 0부터 i까지의 구간에서 합이 target인 부분 배열 중 최소 길이로 정의합니다. 현재 윈도우(left ~ right)가 유효한 부분 배열일 때, 이 부분 배열의 **왼쪽 영역(0 ~ left-1)**에 이미 존재하는 최적의 부분 배열 길이(dp[left-1])와 현재 부분 배열 길이를 더해 정답 후보를 갱신합니다.이 방식은 "현재 부분 배열을 두 번째 부분 배열로 간주하고, 첫 번째 부분 배열은 그 왼쪽에 있는 것 중 가장 짧은 것을 고른다"는 아이디어를 효율적으로 구현합니다.
n = len(arr): 배열 길이dp = [float("inf")] * n: dp[i]는 인덱스 i까지 봤을 때 합이 target인 부분 배열의 최소 길이를 저장. 초깃값은 무한대(inf).left = 0, total = 0: 슬라이딩 윈도우의 왼쪽 포인터와 현재 윈도우 내 원소들의 합.answer = float("inf"): 최종 답안(두 부분 배열 길이 합의 최솟값)을 저장할 변수.for right in range(n))right 포인터를 0부터 n-1까지 이동시키며 total에 arr[right]를 더합니다.while total > target): 합이 target을 초과하면 left 포인터를 오른쪽으로 이동시키며 total에서 arr[left]를 빼줍니다. 양수 배열이므로 합이 커지면 무조건 왼쪽을 잘라내야 합니다.if total == target)현재 윈도우 [left, right]의 합이 target과 일치하면 길이 l = right - left + 1을 계산합니다.
left - 1 인덱스 이전에 있어야 겹치지 않습니다. dp[left-1]에 저장된 이전 구간의 최단 길이와 현재 길이 l을 더해 answer를 갱신합니다. (단, left > 0이고 dp[left-1]이 유효한 값일 때만 수행)right까지의 최단 부분 배열 길이를 dp[right]에 저장합니다. 직전 인덱스까지의 최단 길이(dp[right-1])와 현재 찾은 길이 l 중 최솟값을 취합니다.else)현재 right에서 합이 target이 되는 부분 배열이 끝나지 않았다면, dp[right]는 이전 값 dp[right-1]을 그대로 이어받습니다. (이전까지의 최단 길이가 유지됨)
루프 종료 후 answer가 여전히 inf라면 조건을 만족하는 쌍을 찾지 못한 것이므로 -1을, 그렇지 않다면 answer를 반환합니다.
시간 복잡도: O(N)
right 포인터는 0부터 N-1까지 한 번만 순회합니다.left 포인터 역시 0부터 N-1까지 최대 한 번만 순회합니다 (각 원소는 최대 한 번 윈도우에 들어갔다 나옵니다).공간 복잡도: O(N)
dp 배열을 사용합니다.target인 부분 배열을 중복 없이, 누락 없이 O(N)에 모두 찾을 수 있습니다.dp[i] = i까지의 최단 길이): 현재 찾은 부분 배열의 왼쪽에 있는 최적의 부분 배열 길이를 O(1)에 조회하기 위해 사용합니다. 이로 인해 중첩 루프 없이 선형 시간에 두 번째 부분 배열과의 조합을 확인할 수 있습니다.left이므로, 첫 번째 부분 배열은 left - 1 인덱스 이전에 끝나야 합니다. dp[left-1]을 참조함으로써 자연스럽게 인덱스가 겹치지 않는 조건을 만족시킵니다.class Solution:
def minSumOfLengths(self, arr: list[int], target: int) -> int:
n = len(arr)
dp = [float("inf")] * n
left = 0
total = 0
answer = float("inf")
for right in range(n):
total += arr[right]
while total > target:
total -= arr[left]
left += 1
if total == target:
l = right - left + 1
if left > 0 and dp[left-1] != float("inf"):
answer = min(answer, dp[left-1]+l)
prev = dp[right-1] if right > 0 else float("inf")
dp[right] = min(prev, l)
else:
if right > 0:
dp[right ] = dp[right - 1]
return answer if answer != float("inf") else -1