Julat Jumlah Jumlah Subarray Diisih

1508. Julat Jumlah Jumlah Subarray Diisih

Sederhana

Anda diberi nombor tatasusunan yang terdiri daripada n integer positif. Anda mengira jumlah semua subarray berterusan tidak kosong daripada tatasusunan dan kemudian mengisihnya dalam susunan tidak menurun, mencipta tatasusunan baharu bagi n * (n + 1) / 2 nombor.

Kembalikan jumlah nombor dari indeks kiri ke indeks kanan (diindeks daripada 1), termasuk, dalam tatasusunan baharu. Oleh kerana jawapannya boleh menjadi angka yang besar, kembalikan ia modulo 10⁹ + 7.

Contoh 1:

• Input: nombor = [1,2,3,4], n = 4, kiri = 1, kanan = 5
• Output: 13
• Penjelasan: Semua jumlah subarray ialah 1, 3, 6, 10, 2, 5, 9, 3, 7, 4. Selepas mengisihnya dalam susunan tidak menurun, kita mempunyai tatasusunan baharu [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. Jumlah nombor dari indeks le = 1 hingga ri = 5 ialah 1 + 2 + 3 + 3 + 4 = 13.

Contoh 2:

• Input: nombor = [1,2,3,4], n = 4, kiri = 3, kanan = 4
• Output: 6
• Penjelasan: Tatasusunan yang diberikan adalah sama seperti contoh 1. Kami mempunyai tatasusunan baharu [1, 2, 3, 3, 4, 5, 6, 7, 9, 10]. Jumlah nombor daripada indeks le = 3 hingga ri = 4 ialah 3 + 3 = 6.

Contoh 3:

• Input: nombor = [1,2,3,4], n = 4, kiri = 1, kanan = 10
• Output: 50

Kekangan:

• n == angka.panjang
• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 100
• 1 <= kiri <= kanan <= n * (n + 1) / 2

Petunjuk:

1. Kira semua jumlah dan simpan dalam tatasusunan.
2. Kemudian hanya pergi dari indeks KIRI ke KANAN dan hitung jawapan modulo 1e9 + 7.

Penyelesaian:

Untuk menyelesaikan masalah ini, kita boleh ikuti langkah berikut:

1. Janakan semua kemungkinan jumlah subarray berterusan yang tidak kosong.
2. Isih susunan jumlah yang terhasil.
3. Kira jumlah unsur dari indeks kiri ke indeks kanan (berasaskan 1).
4. Kembalikan modulo hasil 10⁹ + 7.

Mari kita laksanakan penyelesaian ini dalam PHP: 1508. Julat Jumlah Jumlah Subarray Diisih

  
  
  Penjelasan:




Menjana Jumlah Subarray:


Lelaran melalui setiap indeks permulaan i subarray.
Untuk setiap indeks permulaan i, hitung jumlah subarray yang berakhir pada indeks j (di mana j >= i).
Tambahkan setiap jumlah subarray yang dikira pada tatasusunan $sums.



Isih Jumlah:


Gunakan fungsi sort() PHP untuk mengisih tatasusunan $sums dalam susunan tidak menurun.



Menjumlahkan Julat Yang Diperlukan:


Lelar daripada indeks kiri-1 ke indeks kanan-1 (memandangkan masalah menggunakan pengindeksan berasaskan 1).
Kumpulkan jumlah elemen dalam julat ini, berhati-hati menggunakan modulo 109 + 7 untuk mengelakkan limpahan.




Penyelesaian ini dengan cekap menjana semua jumlah subarray, mengisihnya dan mengira jumlah julat yang diperlukan seperti yang dinyatakan.

Pautan Kenalan

Jika anda mendapati siri ini membantu, sila pertimbangkan untuk memberi repositori bintang di GitHub atau berkongsi siaran pada rangkaian sosial kegemaran anda ?. Sokongan anda amat bermakna bagi saya!

Jika anda mahukan kandungan yang lebih berguna seperti ini, sila ikuti saya:


LinkedIn
GitHub



          

            
  

            
        
Atas ialah kandungan terperinci Julat Jumlah Jumlah Subarray Diisih. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!