배열을 분할하는 방법의 수

2270. 배열을 분할하는 방법의 수

난이도:중

주제: 배열, 접두사 합계

길이가 n인 인덱스가 0인 정수 배열이 제공됩니다.

nums는 다음 사항이 참인 경우 인덱스 i에 유효한 분할을 포함합니다.

• 첫 번째 i 1개 요소의 합은 마지막 n - i - 1개 요소의 합 보다 크거나 같습니다.
• i 오른쪽에 적어도 하나 요소가 있습니다. 즉, 0
• 인덱스 2에서 숫자를 나눕니다. 그러면 첫 번째 부분은 [2,3,1]이고 그 합은 6입니다. 두 번째 부분은 [0]이고 그 합은 0입니다. 6>= 0이므로, i = 2는 유효한 분할입니다.

제약조건:

• 2 5
• -10⁵ <= 숫자[i] <= 10⁵

힌트:

1. 모든 인덱스 i에 대해 첫 번째 i 요소의 합에서 첫 번째 (i 1) 요소의 합을 어떻게 찾을 수 있나요?
2. 배열의 총 합을 알고 있는 경우 첫 번째(i 1) 요소의 합이 나머지 요소보다 크거나 같은지 어떻게 확인할 수 있나요?

해결책:

다음 단계를 사용하여 접근할 수 있습니다.

접근하다:

1. 접두사 합: 먼저 왼쪽부터 배열의 누적 합을 계산합니다. 이는 처음 i 1개 요소의 합을 확인하는 데 도움이 됩니다.
2. 총합: 배열의 총합을 계산합니다. 이는 나머지 요소의 합이 처음 i 1개 요소의 합보다 작거나 같은지 확인하는 데 유용합니다.
3. 배열 반복: 각 유효한 인덱스 i(여기서 0 <= i < n-1)에 대해 첫 번째 i 1 요소의 합이 다음의 합보다 크거나 같은지 확인합니다. 마지막 n-i-1 요소입니다.
4. 효율성: 합계를 반복적으로 다시 계산하는 대신 접두사 합계와 합계를 사용하면 효율적인 비교가 가능합니다.

이 솔루션을 PHP: 2270으로 구현해 보겠습니다. 배열을 분할하는 방법의 수

  
  
  설명:




$totalSum: 이 변수는 nums 배열에 있는 모든 요소의 합계를 저장합니다.

$prefixSum: 이 변수는 왼쪽부터(인덱스 i까지) 요소의 누적 합계를 추적합니다.

$remainingSum: 인덱스 i 1부터 배열 끝까지 남은 요소의 합계입니다. $totalSum에서 $prefixSum을 빼서 계산됩니다.

유효한 분할 확인: 각 인덱스 i에 대해 접두어 합계가 나머지 합계보다 크거나 같은지 확인합니다.



  
  
  시간 복잡도:




O(n): 배열을 한 번 반복하여 합계를 계산하고 다시 한 번 유효한 분할을 확인합니다. 따라서 시간 복잡도는 배열 길이에 대해 선형입니다.



  
  
  공간 복잡도:




O(1): 몇 가지 추가 변수($totalSum, $prefixSum, $remainingSum)만 사용하므로 공간 복잡도는 일정합니다.


연락처 링크

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

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


링크드인
깃허브



          

            
  

            
        
위 내용은 배열을 분할하는 방법의 수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!