Longest Subarray with Sum K

+10

정수 배열 nums와 목표값 k가 주어졌을 때, 원소의 합이 정확히 k인 가장 긴 부분 배열의 길이를 반환하세요. 부분 배열은 연속된 원소가 하나 이상 이어진 구간입니다. 값 중에는 0이나 음수가 있을 수 있습니다. 합이 k인 부분 배열이 없으면 0을 반환하세요.

함수

longestSubarrayWithSumK(nums: integer-array, k: integer) → integer

numsinteger-array: 검색할 정수(음수와 0 포함)
kinteger: 부분 배열이 가져야 하는 정확한 합
반환값integer: 합이 k가 되는 가장 긴 부분 배열의 길이. 그런 부분 배열이 없으면 0

제약 조건

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
-10⁹ ≤ k ≤ 10⁹
모든 누적 합은 -2 × 10⁸에서 2 × 10⁸ 사이이므로 32비트 정수로 충분합니다.
어떤 부분 배열의 합도 k가 되지 않으면 0을 반환하세요.

예제

입력: nums = [2, -1, 3, 1, -4, 2, 3]k = 5
출력: 5
설명: 세 개의 연속 구간의 합은 5입니다. 끝에서 시작하는 [2, 3], 시작에서 시작하는 [2, -1, 3, 1], 인덱스 2부터 6까지의 [3, 1, -4, 2, 3]입니다. 마지막 구간이 가장 길며, 원소가 5개입니다.

입력: nums = [4, 1, 1, 2, -1, 1]k = 3
출력: 4
설명: 인덱스 1부터 4까지의 [1, 1, 2, -1]과 인덱스 2부터 5까지의 [1, 2, -1, 1]은 모두 원소가 4개이고 합이 3입니다. 길이를 반환하므로 동점은 상관없습니다.

후속 질문

음수 값도 허용하면서 합이 k 이하인 가장 긴 부분 배열을 어떻게 찾을 수 있을까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

누적 합을 사용하면 모든 부분 배열의 합을 한 번의 뺄셈으로 구할 수 있습니다. 인덱스 s 다음부터 인덱스 i까지의 원소 합은 prefix[i] - prefix[s]입니다. 각 누적 합이 처음 나타나는 인덱스를 기억하면, 한 번의 순회로 각 위치에서 끝나는 가장 긴 일치 구간을 찾을 수 있습니다.

각 시작점에서 모든 부분 배열을 확장하세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

각 시작점에서 오른쪽으로 확장하면서 각 원소를 누적 합계에 더합니다. 합계가 k와 같아질 때마다 길이를 기록합니다. 모든 부분 배열은 시작점과 끝점의 한 쌍이므로 빠뜨리는 경우가 없습니다. 합계가 k를 넘은 뒤에도 계속 확장합니다. 첫 번째 예시에서 인덱스 2부터의 합계는 3, 4, 0, 2, 5이며, 마지막 합계가 5에 도달하는 이유는 -4입니다.

쌍은 약 n²/2개입니다. n = 2 × 10^4이면 덧셈은 2 × 10^8회입니다.

알고리즘

best를 0으로 설정합니다.
각 start에 대해 total을 0으로 설정합니다.
end를 start부터 마지막 인덱스까지 이동시키고 nums[end]를 total에 더합니다.
total이 k와 같으면 best와 end - start + 1 중 더 큰 값으로 best를 설정합니다.
best를 반환합니다.

def longestSubarrayWithSumK(nums, k):
    n = len(nums)
    best = 0
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            # A match may come after the total has passed k, so never stop early
            if total == k and end - start + 1 > best:
                best = end - start + 1
    return best

각 합의 첫 번째 인덱스를 사용한 누적 합

핵심 아이디어

인덱스 i에서 끝나는 구간의 합이 k가 되는 것은 이전 누적합 중 하나가 prefix - k와 같을 때뿐입니다. 조건을 만족하는 이전 누적합이 여러 개라면 가장 먼저 나타난 누적합이 가장 긴 구간의 시작점이 되므로, 맵에는 각 누적합이 처음 나타날 때만 저장합니다. 나중에 나타난 같은 누적합은 더 짧은 구간의 시작점이 될 뿐입니다. 인덱스 -1에서 누적합 0으로 맵을 초기화하면, 인덱스 0에서 시작하는 구간이 조건을 만족할 때 길이는 i + 1이 됩니다.

첫 번째 예제에서 누적합은 2, 1, 4, 5, 1, 3, 6입니다. 인덱스 6에서 6 - 5 = 1이고, 1은 인덱스 1에서 처음 나타났으므로 구간의 길이는 5입니다. 누적합 1은 인덱스 4에서 다시 나타나지만, 인덱스 1을 유지해야 해당 구간을 찾을 수 있습니다.

각 요소마다 조회를 한 번씩 수행하므로 시간 복잡도는 O(n)이고, 맵에는 최대 n + 1개의 누적합이 저장됩니다.

알고리즘

인덱스 -1에서 합계가 0인 맵 first를 만들고, prefix와 best를 0으로 설정합니다.
각 인덱스 i에 대해 nums[i]를 prefix에 더합니다.
prefix - k가 맵에 인덱스 start로 존재하면, best와 i - start 중 더 큰 값으로 best를 설정합니다.
prefix가 아직 맵에 없으면 인덱스 i와 함께 저장합니다.
best를 반환합니다.

def longestSubarrayWithSumK(nums, k):
    # first[p] is the index where the prefix sum p first appears; the empty prefix sits at -1
    first = {0: -1}
    prefix = 0
    best = 0
    for i, num in enumerate(nums):
        prefix += num
        # The earliest prefix equal to prefix - k starts the longest match that ends at i
        start = first.get(prefix - k)
        if start is not None and i - start > best:
            best = i - start
        # Keep the first index only: a later one could only start a shorter subarray
        if prefix not in first:
            first[prefix] = i
    return best

함정과 경계 사례

합계가 반복될 때마다 저장된 인덱스를 덮어쓰면 가장 최근 시작 위치가 유지되어 더 짧은 일치 구간을 찾습니다. 첫 번째 예제에서는 합계 1이 인덱스 1에서 인덱스 4로 이동하므로 5가 아니라 4를 반환합니다.
합계가 k보다 클 때 윈도우를 줄이는 방식도 첫 번째 예제에서 4를 반환합니다. 윈도우는 합계가 4인 [-1, 3, 1, -4, 2, 3]을 포함한 상태로 끝나며 -1을 절대 제거하지 않습니다.
인덱스 -1에서 합계 0을 제외하면 인덱스 0에서 시작하는 모든 일치 구간을 놓칩니다. k = 5일 때 [5, 0, 0, 0]은 4가 아니라 0을 반환합니다.
저장된 인덱스는 부분 배열 바로 앞의 위치이므로 길이는 i - start입니다. 1을 더하면 원소를 하나 더 세게 됩니다.

자주 묻는 질문3

합이 K인 최장 부분 배열의 시간 복잡도는 얼마인가요?

누적 합계와 최초 인덱스 맵을 사용하면 시간 O(n), 추가 공간 O(n)이 듭니다. 각 요소마다 조회 한 번과 삽입 최대 한 번이 필요합니다. 각 시작점에서 모든 부분 배열을 늘려 가면 시간 O(n²), 공간 O(1)이 듭니다.

배열에 음수가 있으면 슬라이딩 윈도우는 왜 실패할까요?

슬라이딩 윈도우는 요소를 추가하면 합계가 커지고 요소를 제거하면 합계가 작아진다고 가정합니다. 음수 값이 있으면 합계가 너무 큰 윈도우도 음수 요소가 들어오면 k에 도달할 수 있고, 합계가 너무 작은 윈도우는 왼쪽의 음수 요소를 제거해야 할 수도 있습니다. 윈도우만으로는 어떤 동작이 옳은지 알 수 없습니다.

K 합을 갖는 최장 부분 배열 문제를 추가 공간 O(1)로 해결할 수 있나요?

음수 값이 없을 때만 가능합니다. 그러면 윈도우가 커져도 합이 절대 줄어들지 않으며, 두 포인터를 사용해 O(n) 시간과 O(1) 공간으로 합이 k인 가장 긴 윈도우를 찾을 수 있습니다. 음수 값이 있으면 누적 합 맵이나 O(n²) 탐색이 필요합니다.

def longestSubarrayWithSumK(nums, k):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자들

nums = [2, -1, 3, 1, -4, 2, 3]
k = 5

예상 출력