Bereichssumme sortierter Subarray-Summen

1508. Bereichssumme sortierter Subarray-Summen

Mittel

Sie erhalten die Array-Zahlen bestehend aus n positiven Ganzzahlen. Sie haben die Summe aller nicht leeren kontinuierlichen Unterarrays aus dem Array berechnet und sie dann in nicht absteigender Reihenfolge sortiert, wodurch ein neues Array mit n * (n + 1) / 2 Zahlen erstellt wurde.

Gib die Summe der Zahlen vom Index links zum Index rechts (indiziert ab 1) einschließlich im neuen Array zurück. Da die Antwort eine große Zahl sein kann, geben Sie sie modulo 10⁹ + 7.

zurück

Beispiel 1:

• Eingabe: nums = [1,2,3,4], n = 4, links = 1, rechts = 5
• Ausgabe: 13
• Erklärung: Alle Subarray-Summen sind 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. Nachdem wir sie in nicht absteigender Reihenfolge sortiert haben, haben wir das neue Array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. Die Summe der Zahlen vom Index le = 1 bis ri = 5 ist 1 + 2 + 3 + 3 + 4 = 13.

Beispiel 2:

• Eingabe: nums = [1,2,3,4], n = 4, links = 3, rechts = 4
• Ausgabe: 6
• Erklärung: Das angegebene Array ist das gleiche wie Beispiel 1. Wir haben das neue Array [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. Die Summe der Zahlen vom Index le = 3 bis ri = 4 ist 3 + 3 = 6.

Beispiel 3:

• Eingabe: nums = [1,2,3,4], n = 4, links = 1, rechts = 10
• Ausgabe: 50

Einschränkungen:

• n == nums.length
• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 100
• 1 <= links <= rechts <= n * (n + 1) / 2

Hinweis:

1. Berechnen Sie alle Summen und speichern Sie sie im Array.
2. Dann gehen Sie einfach vom LINKEN zum RECHTEN Index und berechnen Sie die Antwort modulo 1e9 + 7.

Lösung:

Um dieses Problem zu lösen, können wir die folgenden Schritte ausführen:

1. Generieren Sie alle möglichen Summen nicht leerer kontinuierlicher Unterarrays.
2. Sortieren Sie das resultierende Array von Summen.
3. Berechnen Sie die Summe der Elemente vom linken Index zum rechten Index (1-basiert).
4. Gibt das Ergebnis Modulo 10 zurück⁹ + 7.

Lassen Sie uns diese Lösung in PHP implementieren: 1508. Bereichssumme sortierter Subarray-Summen

  
  
  Erläuterung:




Subarray-Summen generieren:


Durchlaufen Sie jeden Startindex i des Subarrays.
Berechnen Sie für jeden Startindex i die Summe der Subarrays, die bei Index j enden (wobei j >= i).
Hängen Sie jede berechnete Subarray-Summe an das $sums-Array an.



Sortieren der Summen:


Verwenden Sie die Funktion sort() von PHP, um das Array $sums in nicht absteigender Reihenfolge zu sortieren.



Summierung des erforderlichen Bereichs:


Iterieren Sie vom linken 1-Index zum rechten 1-Index (da das Problem eine 1-basierte Indizierung verwendet).
Akkumulieren Sie die Summe der Elemente in diesem Bereich und achten Sie darauf, Modulo 109 + 7 zu verwenden, um einen Überlauf zu vermeiden.




Diese Lösung generiert effizient alle Subarray-Summen, sortiert sie und berechnet die erforderliche Bereichssumme wie angegeben.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:


LinkedIn
GitHub



          

            
  

            
        
Das obige ist der detaillierte Inhalt vonBereichssumme sortierter Subarray-Summen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!