정렬된 하위 배열 합계의 범위 합계

1508. 정렬된 하위 배열 합계의 범위 합계

중간

n개의 양의 정수로 구성된 배열 nums가 제공됩니다. 배열에서 비어 있지 않은 모든 연속 하위 배열의 합을 계산한 다음 이를 내림차순으로 정렬하여 n * (n + 1) / 2 숫자의 새 배열을 생성했습니다.

새 배열에서 왼쪽 인덱스부터 오른쪽 인덱스(1부터 인덱스화됨)까지의 숫자 합계를 반환합니다^{. 답은 엄청난 숫자일 수 있으므로 모듈로 10}9

+ 7을 반환합니다.

예 1:

• 입력:
nums = [1,2,3,4], n = 4, 왼쪽 = 1, 오른쪽 = 5
• 출력:
13
• 설명:
모든 하위 배열 합계는 1, 3, 6, 10, 2, 5, 9, 3, 7, 4입니다. 이를 내림차순으로 정렬한 후 새로운 배열 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. 인덱스 le = 1부터 ri = 5까지의 숫자의 합은 1 + 2 + 3 + 3 + 4 = 13입니다.

예 2:

• 입력:
nums = [1,2,3,4], n = 4, 왼쪽 = 3, 오른쪽 = 4
• 출력:
6
• 설명:
주어진 배열은 예제 1과 동일합니다. 새로운 배열 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]이 있습니다. 인덱스 le = 3부터 ri = 4까지의 숫자의 합은 3 + 3 = 6입니다.

예 3:

• 입력:
nums = [1,2,3,4], n = 4, 왼쪽 = 1, 오른쪽 = 10
• 출력:
50

제약조건:

n == 숫자.길이
1 <= nums.length <= 1000
1 <= 숫자[i] <= 100
1 <= 왼쪽 <= 오른쪽 <= n * (n + 1) / 2

힌트:

모든 합계를 계산하고 배열에 저장합니다.
그런 다음 왼쪽에서 오른쪽 인덱스로 이동하여 모듈로 1e9 + 7로 답을 계산하세요.

해결책:

이 문제를 해결하려면 다음 단계를 따르세요.

비어 있지 않은 연속 하위 배열의 가능한 모든 합을 생성합니다.
결과 합계 배열을 정렬합니다.
왼쪽 인덱스부터 오른쪽 인덱스까지 요소의 합을 계산합니다(1부터 시작).
4. ^{결과를 모듈로 10}9
+ 7로 반환합니다.

PHP에서 이 솔루션을 구현해 보겠습니다. 1508. 정렬된 하위 배열 합계의 범위 합계

  
  
  설명:





하위 배열 합계 생성:



하위 배열의 각 시작 인덱스 i를 반복합니다.

각 시작 인덱스 i에 대해 인덱스 j에서 끝나는 하위 배열의 합을 계산합니다(여기서 j >= i).

계산된 각 하위 배열 합계를 $sums 배열에 추가합니다.



합계 정렬:



PHP의 sort() 함수를 사용하여 $sums 배열을 내림차순으로 정렬합니다.



필요한 범위 합산:



left-1 인덱스에서 right-1 인덱스로 반복합니다(문제가 1 기반 인덱싱을 사용하므로).

오버플로를 방지하려면 모듈로 109
 + 7을 사용하여 이 범위에 있는 요소의 합을 누적하세요.




이 솔루션은 모든 하위 배열 합계를 효율적으로 생성하고 정렬하며 지정된 대로 필요한 범위 합계를 계산합니다.


연락처 링크


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


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



링크드인

깃허브




          

            
  

            
        
위 내용은 정렬된 하위 배열 합계의 범위 합계의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!