배열을 분할하는 방법의 수

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

난이도:중

주제: 배열, 접두사 합계

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

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

• 첫 번째 i 1개 요소의 합은 마지막 n - i - 1개 요소의 합 보다 크거나 같습니다.
• i 오른쪽에 적어도 하나 요소가 있습니다. 즉, 0

유효한 분할 수를 숫자로 반환합니다.

예 1:

• 입력: 숫자 = [10,4,-8,7]
• 출력: 2
• 설명: 숫자를 비어 있지 않은 두 부분으로 나누는 세 가지 방법이 있습니다.
  • 인덱스 0에서 숫자를 나눕니다. 그런 다음 첫 번째 부분은 [10]이고 그 합은 10입니다. 두 번째 부분은 [4,-8,7]이고 그 합은 3입니다. 10 ≥ 3이므로 , i = 0은 유효한 분할입니다.
  • 인덱스 1에서 숫자를 나눕니다. 그런 다음 첫 번째 부분은 [10,4]이고 그 합은 14입니다. 두 번째 부분은 [-8,7]이고 합은 -1입니다. 14 >= -1이므로 i = 1이 유효한 분할입니다.
  • 인덱스 2에서 숫자를 나눕니다. 그러면 첫 번째 부분은 [10,4,-8]이고 그 합은 6입니다. 두 번째 부분은 [7]이고 그 합은 7입니다. 7, i = 2는 유효한 분할이 아닙니다.
  • 따라서 숫자로 표시되는 유효한 분할 수는 2입니다.

예 2:

• 입력: 숫자 = [2,3,1,0]
• 출력: 2
• 설명: 숫자에는 두 가지 유효한 분할이 있습니다.
  • 인덱스 1에서 숫자를 나눕니다. 그러면 첫 번째 부분은 [2,3]이고 그 합은 5입니다. 두 번째 부분은 [1,0]이고 그 합은 1입니다. 5>= 1이므로, i = 1은 유효한 분할입니다.
  • 인덱스 2에서 숫자를 나눕니다. 그러면 첫 번째 부분은 [2,3,1]이고 그 합은 6입니다. 두 번째 부분은 [0]이고 그 합은 0입니다. 6>= 0이므로, i = 2는 유효한 분할입니다.

제약조건:

• 2 5
• -10⁵ 5

힌트:

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

해결책:

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

접근하다:

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

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

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

// Example usage:
$nums1 = [10, 4, -8, 7];
echo waysToSplitArray($nums1); // Output: 2

$nums2 = [2, 3, 1, 0];
echo waysToSplitArray($nums2); // Output: 2
?>

설명:

1. $totalSum: 이 변수는 nums 배열에 있는 모든 요소의 합계를 저장합니다.
2. $prefixSum: 이 변수는 왼쪽부터(인덱스 i까지) 요소의 누적 합계를 추적합니다.
3. $remainingSum: 인덱스 i 1부터 배열 끝까지 남은 요소의 합계입니다. $totalSum에서 $prefixSum을 빼서 계산됩니다.
4. 유효한 분할 확인: 각 인덱스 i에 대해 접두어 합계가 나머지 합계보다 크거나 같은지 확인합니다.

시간 복잡도:

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

공간 복잡도:

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

연락처 링크

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

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

• 링크드인
• 깃허브

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