. 합이 최소 K인 최단 하위 배열

862. 합이 최소 K인 최단 하위 배열

난이도:어려움

주제: 배열, 이진 검색, 큐, 슬라이딩 윈도우, 힙(우선순위 큐), 접두사 합계, 단조 큐

정수 배열 nums와 정수 k가 주어지면 최소 k의 합을 갖는 nums의 비어 있지 않은 가장 짧은 길이 하위 배열을 반환합니다. 해당 하위 배열이 없으면 -1을 반환합니다.

하위 배열은 배열의 인접 부분입니다.

예 1:

• 입력: nums = [1], k = 1
• 출력: 1

예 2:

• 입력: nums = [1,2], k = 4
• 출력: -1

예 3:

• 입력: nums = [2,-1,2], k = 3
• 출력: 3

제약조건:

• 1 5
• -10⁵ 5
• 1 9

해결책:

접두사 합계 및 단조 대기열과 결합된 슬라이딩 윈도우 접근 방식을 사용해야 합니다. 단계별 접근 방식은 다음과 같습니다.

단계:

1. 접두사 합계:

   • 먼저, 접두사 합계 배열을 계산합니다. 여기서 인덱스 i의 각 요소는 배열 시작부터 i까지 요소의 합을 나타냅니다. 접두어 sum을 사용하면 일정한 시간에 모든 하위 배열의 합을 계산할 수 있습니다.

2. 단조 대기열:

   • prefix_sum 배열의 인덱스를 유지하기 위해 deque(양단 큐)를 사용합니다. deque는 접두사 합계가 증가하는 순서로 유지됩니다.
   • 이는 현재 접두사 합과 이전 접두사 합을 비교하여 합이 k보다 크거나 같은 하위 배열을 효율적으로 찾는 데 도움이 됩니다.

3. 슬라이딩 윈도우 로직:

   • 각 인덱스 i에 대해 현재 접두사 합계와 이전 접두사 합계(deque에 저장됨) 간의 차이가 k보다 크거나 같은지 확인합니다.
   • 그렇다면 하위 배열의 길이를 계산하고 필요한 경우 최소 길이를 업데이트하세요.

연산:

1. prefix_sum 배열을 크기 n 1(여기서 n은 입력 배열의 길이)로 초기화합니다. 0개 요소의 합이 0이기 때문에 첫 번째 요소는 0입니다.
2. deque를 사용하여 prefix_sum 값의 인덱스를 저장합니다. 데크는 조건을 만족하는 가장 짧은 하위 배열을 효율적으로 찾는 데 도움이 됩니다.
3. 배열의 각 요소에 대해 prefix_sum을 업데이트하고 deque를 확인하여 합이 k보다 크거나 같은 가장 작은 하위 배열을 찾습니다.

이 솔루션을 PHP로 구현해 보겠습니다. 862. 합이 최소 K인 최단 하위 배열

<?php /**
 * @param Integer[] $nums
 * @param Integer $k
 * @return Integer
 */
function shortestSubarray($nums, $k) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums1 = [1];
$k1 = 1;
echo shortestSubarray($nums1, $k1) . "\n"; // Output: 1

$nums2 = [1, 2];
$k2 = 4;
echo shortestSubarray($nums2, $k2) . "\n"; // Output: -1

$nums3 = [2, -1, 2];
$k3 = 3;
echo shortestSubarray($nums3, $k3) . "\n"; // Output: 3
?>

설명:

1. 접두사 합계 배열:

   • prefix_sum 배열에서 배열의 누적 합계를 계산합니다. 이는 prefix_sum[j 1] - prefix_sum[i] 공식을 사용하여 하위 배열 nums[i...j]의 합계를 계산하는 데 도움이 됩니다.

2. 단조 대기열:

   • deque는 값의 오름차순으로 prefix_sum 배열의 인덱스를 보유합니다. 합이 k보다 크거나 같은 가장 작은 하위 배열을 효율적으로 찾을 수 있도록 이 순서를 유지합니다.

3. 슬라이딩 윈도우 로직:

   • prefix_sum 배열을 탐색하면서 현재 prefix_sum[i]와 이전 prefix_sum[deque[0]] 간의 차이를 사용하여 가장 작은 하위 배열을 찾으려고 합니다.
   • 차이가 k보다 크거나 같으면 하위 배열 길이를 계산하고 발견된 최소 길이를 업데이트합니다.

4. 반환 결과:

   • 유효한 하위 배열이 없으면 -1을 반환합니다. 그렇지 않으면 최소 하위 배열 길이를 반환합니다.

시간 복잡도:

• 시간 복잡도: O(n), 여기서 n은 입력 배열의 길이입니다. 각 요소는 최대 두 번 처리됩니다(deque에 추가할 때 한 번, 제거할 때 한 번).
• 공간 복잡도: prefix_sum 배열과 인덱스를 저장하는 데 사용되는 데크 때문에 O(n)입니다.

이 접근 방식을 사용하면 대규모 입력에도 솔루션이 효율적으로 실행됩니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 . 합이 최소 K인 최단 하위 배열의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!