길이가 K인 개별 하위 배열의 최대 합

2461. 길이가 K인 고유 하위 배열의 최대 합

난이도:중

주제: 배열, 해시 테이블, 슬라이딩 윈도우

정수 배열 nums와 정수 k가 주어졌습니다. 다음 조건을 충족하는 모든 하위 배열의 최대 하위 배열 합계를 찾습니다.

• 하위 배열의 길이는 k이고
• 하위 배열의 모든 요소는 구별됩니다.

조건을 충족하는 모든 하위 배열의 최대 하위 배열 합계를 반환합니다. 조건을 충족하는 하위 배열이 없으면 0을 반환합니다.

하위 배열은 배열 내 비어 있지 않은 연속된 요소 시퀀스입니다.

예 1:

• 입력: nums = [1,5,4,2,9,9,9], k = 3
• 출력: 15
• 설명: 길이가 3인 숫자의 하위 배열은 다음과 같습니다.
  • [1,5,4]는 요구 사항을 충족하고 합이 10입니다.
  • [5,4,2]는 요구 사항을 충족하고 합이 11입니다.
  • [4,2,9]는 요구 사항을 충족하고 합이 15입니다.
  • [2,9,9]는 9번 요소가 반복되어 요구사항을 충족하지 않습니다.
  • [9,9,9]는 9번 요소가 반복되어 요구사항을 충족하지 않습니다.
  • 조건을 충족하는 모든 하위 배열의 최대 하위 배열 합계인 15를 반환합니다

예 2:

• 입력: nums = [4,4,4], k = 3
• 출력: 0
• 설명: 길이가 3인 숫자의 하위 배열은 다음과 같습니다.
  • [4,4,4]는 4번 요소가 반복되어 요구사항을 충족하지 않습니다.
  • 조건을 충족하는 하위 배열이 없기 때문에 0을 반환합니다.

제약조건:

• 1 <= k <= nums.length <= 10⁵
• 1 <= 숫자[i] <= 10⁵

힌트:

1. 인덱스 i에서 끝나는 크기 k의 하위 배열에서 인덱스 i 1로 끝나는 크기 k의 하위 배열로 이동할 때 어떤 요소가 변경되나요?
2. 두 개의 요소만 변경됩니다. i 1의 요소는 하위 배열에 추가되고 i - k 1의 요소는 하위 배열에서 제거됩니다.
3. 크기가 k인 각 하위 배열을 반복하고 하위 배열의 합과 각 요소의 빈도를 추적합니다.

해결책:

다음 단계를 따르세요.

접근하다:

1. 슬라이딩 윈도우: 윈도우 크기는 k이고, 현재 윈도우의 합을 유지하면서 윈도우의 모든 요소가 서로 다른지 확인하면서 배열을 통해 윈도우를 슬라이드합니다.
2. 해시 테이블(또는 연관 배열): 연관 배열(해시 테이블)을 사용하여 현재 창에 있는 요소의 빈도를 추적합니다. 요소가 두 번 이상 나타나면 해당 창이 유효하지 않습니다.
3. 창 업데이트: 창을 슬라이드하면서 새 요소(즉, 창으로 들어오는 요소)를 추가하고 이전 요소(즉, 창을 떠나는 요소)를 제거합니다. 그에 따라 합계를 업데이트하고 창이 유효한지(즉, 모든 요소가 고유한지) 확인하세요.
4. 최대 합계 반환: 유효한 하위 배열 중에서 발견되는 최대 합계를 추적해야 합니다.

연산:

1. 해시 테이블 freq를 초기화하여 현재 창의 요소 빈도를 저장합니다.
2. 크기가 k인 첫 번째 창에 대한 합계를 계산하는 것부터 시작하고 창에 개별 요소가 포함되어 있으면 결과를 저장합니다.
3. 다음 방법으로 창을 왼쪽에서 오른쪽으로 밉니다.
   • 왼쪽에서 창을 벗어나는 요소를 제거합니다.
   • 오른쪽에서 창으로 들어가는 요소를 추가합니다.
   • 합산 테이블과 해시 테이블을 업데이트하고 창에 여전히 고유한 요소만 포함되어 있는지 확인하세요.
4. 창에 유효한 개별 요소가 있는 경우 최대 합계를 업데이트하세요.
5. 유효한 하위 배열이 발견되지 않으면 0을 반환합니다.

이 솔루션을 PHP로 구현해 보겠습니다: 2461. 길이가 K인 고유 하위 배열의 최대 합

  
  
  설명:




변수:



$maxSum: 지금까지 발견된 유효한 하위 배열의 최대 합계를 추적합니다.

$currentSum: k 크기의 현재 슬라이딩 윈도우의 합계를 보유합니다.

$freq: 현재 창의 요소 빈도를 저장하는 해시 테이블(또는 연관 배열)입니다.



슬라이딩 창:


루프를 사용하여 배열을 반복합니다. 창을 이동하면 다음이 수행됩니다.


$i 인덱스의 요소를 합계에 추가하고 빈도를 업데이트합니다.
창 크기가 k를 초과하면 합계에서 인덱스 $i - k에 있는 요소를 제거하고 빈도를 줄입니다.





유효한 창 확인:


창 크기가 k에 도달하면(즉, $i >= k - 1인 경우) 주파수 맵의 개별 키 수가 k와 같은지 확인하여 창의 모든 요소가 고유한지 확인합니다. 그렇다면 최대 합계를 업데이트합니다.



결과 반환:

배열을 반복한 후 찾은 최대 합계를 반환합니다. 유효한 하위 배열이 발견되지 않으면 maxSum은 0으로 유지됩니다.





  
  
  시간 복잡도:




O(n), 여기서 n은 nums 배열의 길이입니다. 각 요소는 슬라이딩 윈도우에 한 번씩 추가되고 제거되며, 해시 테이블 연산(삽입, 제거, 확인 횟수)은 평균 O(1)입니다.



  
  
  공간 복잡도:




O(k) 현재 창의 요소 빈도를 저장하는 해시 테이블의 경우


연락처 링크

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

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


링크드인
깃허브



          

            
  

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