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 kanan indeks (diindeks daripada 1), termasuk, dalam tatasusunan baharu. Oleh kerana jawapannya boleh menjadi jumlah yang besar, pulangkan ia modulo 10⁹ + 7.

Contoh 1:

• Input: angka = [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: angka = [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 dari indeks le = 3 hingga ri = 4 ialah 3 + 3 = 6.

Contoh 3:

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

Kekangan:

• n == bilangan.panjang
• 1 <= nums.length <= 1000
• 1 <= angka[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. Jana 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 hasil modulo 10⁹ + 7.

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

  
  
  Penjelasan:




Menjana Jumlah Subarray:


Lelar 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 dari indeks kiri-1 ke indeks-1 kanan (kerana masalah menggunakan pengindeksan berasaskan 1).
Kumpulkan jumlah elemen dalam julat ini, berhati-hati menggunakan modulo 109 + 7 untuk mengelakkan limpahan.




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

Hubungi Pautan

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 buat 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!