2270. 배열 분할 방법

난이도 : medium

주제 : 배열, 접두사 합

당신은 0-indexed 정수 배열 길이 n.

nums는 다음이 사실이라면 색인 I에서 유효한 분할 을 포함합니다.

• 첫 번째 i 1 요소의 합은 이 마지막 n -i -1 요소의 합의 보다 크거나 동일합니다.
i의 오른쪽에
• 가 하나 이상의 요소가 있습니다. 즉, 0

유효한 스플릿의 수 nums .

예 1 :

• 입력 : nums = [10,4, -8,7]
• 출력 : 2
• 설명 : 인덱스 0에서 나오는 NUMS를 분할 한 다음 첫 번째 부분은 [10]이고 합계는 10입니다. 두 번째 부분은 [4, -8,7]이고 합은 3입니다. 10> = 3이므로 i = 0은 유효한 분할입니다.
  • 인덱스 1에서 나오는 Nums를 분할 한 다음 첫 번째 부분은 [10,4]이고 합은 14입니다. 두 번째 부분은 [-8,7]이고 합은 -1입니다. 14> = -1 이후 i = 1은 유효한 분할입니다.
  • 인덱스 2에서 나오는 Nums를 분할했습니다. 그런 다음 첫 번째 부분은 [10,4, -8]이고 합계는 6입니다. 두 번째 부분은 [7]이고 합계는 7입니다. 6 따라서, Nums의 유효한 분할 수는 2입니다.
예 2 :

nums = [2,3,1,0]
• 출력 :
2
• 설명 :
Nums에는 두 가지 유효한 분할이 있습니다.
• 인덱스 1에서 분할 Nums. 그런 다음 첫 번째 부분은 [2,3]이고 합계는 5입니다. 두 번째 부분은 [1,0]이고 합계는 1입니다. 5> = 1이므로 i = 1은 유효한 분할입니다.
  인덱스 2에서 나오는 Nums를 분할했습니다. 그런 다음 첫 번째 부분은 [2,3,1]이고 합계는 6입니다. 두 번째 부분은 [0]이고 합계는 0입니다. 6> = 0이므로 i = 2는 유효한 분할입니다.
제약 조건 :

2 5

• ^-10 5
5 힌트:

모든 색인 i의 경우, 첫 번째 I 요소의 합에서 첫 번째 (I 1) 요소의 합을 어떻게 찾을 수 있습니까?

배열의 총 합이 알려진 경우, 첫 번째 (I 1) 요소의 합이 나머지 요소보다 크거나 같은지 확인할 수 있습니까?
2. 해결책:

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

: 먼저, 우리는 왼쪽에서 배열의 누적 합을 계산하여 첫 번째 i 1 요소의 합을 확인하는 데 도움이됩니다.
1. 총 합
: 배열의 총 합을 계산합니다. 이는 나머지 요소의 합이 첫 I 1 요소의 합보다 작거나 같은지 확인하는 데 유용합니다.
2. 배열을 반복
: 각 유효한 인덱스 i (여기서 0 효율성 : 합계를 반복적으로 재 계산하는 대신 효율적인 비교를 위해 접두사 합과 총 합을 사용하십시오.
3. PHP 에서이 솔루션을 구현하겠습니다 :
2270. 배열 분할 방법

php /** * @Param Integer [] $ nums * @return Integer */ 함수 waystosplitArray ($ nums) { ... ... ... /** * ./solution.php로 이동하십시오 */ } // 예제 사용 : $ nums1 = [10, 4, -8, 7]; echo waystosplitarray ($ nums1); // 출력 : 2 $ nums2 = [2, 3, 1, 0]; echo waystosplitarray ($ nums2); // 출력 : 2 ?>

:이 변수는 Nums 배열에 모든 요소의 합을 저장합니다.
1. $ prefixsum
:이 변수는 왼쪽에서 요소의 누적 합계를 추적합니다 (INDEX I까지).
2. $ 남은 상태
: 이것은 색인 i 1에서 배열 끝까지 나머지 요소의 합입니다. $ totalsum에서 $ prefixsum을 빼서 계산됩니다.
3. 유효한 분할 점검
: 각 인덱스 i에 대해 접두사 합이 나머지 합계보다 크든 동일인지 확인합니다.
4. 시간 복잡성 :

: 우리는 배열을 한 번 반복하여 합을 계산하고 유효한 스플릿을 다시 확인합니다. 따라서 시간 복잡성은 배열의 길이와 관련하여 선형입니다.
• 공간 복잡성 :

: 우리는 몇 가지 추가 변수 만 사용하고 있습니다 ($ thantalsum, $ prefixsum, $ 남은 남은). 공간 복잡성은 일정합니다.
연락처 링크

이 시리즈가 도움이된다면 리포지토리

이와 같은 유용한 컨텐츠를 원한다면 언제든지 나중하십시오 :

• github