Running Sum of an Array

Q: Apa jumlah kumulatif dari sebuah array?

Ini adalah array kedua yang setiap elemennya merupakan total dari semua elemen hingga dan termasuk posisi yang sama pada array pertama. Ini juga disebut jumlah awalan atau jumlah kumulatif. Jumlah berjalan dari [3, 1, 4, 1, 5] adalah [3, 4, 8, 9, 14] .

Q: Apa kompleksitas waktu untuk menghitung jumlah kumulatif?

Waktu O(n) dengan satu total yang dibawa dari kiri ke kanan, dan ruang tambahan O(1) selain jawaban. Menghitung ulang setiap prefiks dari awal membutuhkan O(n²) .

Q: Bisakah kamu menghitung jumlah kumulatif secara langsung?

Ya. Telusuri dari indeks 1 hingga akhir dan atur nums[i] += nums[i-1] . Saat itu, nums[i-1] sudah menyimpan total semua nilai hingga indeks tersebut, sehingga setiap elemen berakhir sebagai jumlah prefiksnya. Nilai aslinya akan hilang.

Q: Bagaimana prefix sum membantu menjawab kueri jumlah rentang?

Jumlah slice nums[l..r] adalah prefix[r] - prefix[l-1] , atau prefix[r] saat l = 0 . Dengan [3, 4, 8, 9, 14] , indeks 2 hingga 4 berjumlah 14 - 4 = 10 . Setiap kueri membutuhkan O(1) setelah satu pemindaian O(n) .

PemulaPrefix sum

+10

Kamu mendapatkan array bilangan bulat nums. Kembalikan array baru dengan panjang yang sama, dengan elemen pada indeks i bernilai nums[0] + nums[1] + ... + nums[i], yaitu jumlah dari i+1 bilangan pertama.

Fungsi

runningSum(nums: integer-array) → integer-array

numsinteger-array: angka-angka yang dijumlahkan dari kiri ke kanan
Mengembalikaninteger-array: total berjalan, satu untuk setiap elemen nums

Batasan

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
Setiap total berjalan muat dalam integer bertanda 32-bit.

Contoh

Input: nums = [3, 1, 4, 1, 5]
Output: [3, 4, 8, 9, 14]
Penjelasan: Terus tambahkan: 3, lalu 3 + 1 = 4, 4 + 4 = 8, 8 + 1 = 9, dan 9 + 5 = 14. Setiap total dimasukkan ke indeks angka yang terakhir ditambahkan.

Input: nums = [-2, 5, -3]
Output: [-2, 3, 0]
Penjelasan: Bilangan negatif menurunkan total: -2, lalu -2 + 5 = 3, lalu 3 + (-3) = 0.

Input: nums = [7]
Output: [7]
Penjelasan: Satu angka memiliki satu total berjalan, yaitu dirinya sendiri, jadi jawabannya adalah [7].

Pertanyaan lanjutan

Bisakah kamu membuat hal yang sama untuk grid, dengan setiap sel menyimpan total persegi panjang dari sudut kiri atas hingga sel tersebut?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Setiap jawaban adalah jumlah dari prefiks nums, dan prefiks yang bersebelahan berbeda satu elemen. Menghitung ulang setiap prefiks dari awal mengulang hampir semua pekerjaan. Sebaliknya, teruskan satu total dan setiap jawaban hanya memerlukan satu penjumlahan.

Jumlahkan setiap prefiks dari awal

Intuisi

Ikuti definisinya: untuk setiap indeks i, mulai dengan total 0, tambahkan nums[0] hingga nums[i], lalu simpan hasilnya. Cara ini benar karena setiap jawaban dihitung persis sesuai definisi.

Indeks i memerlukan i+1 penjumlahan, jadi array memerlukan n(n+1)/2: sekitar 1.25 × 10^7 penjumlahan untuk n = 5000, dan 5000 masih bisa digunakan.

Algoritma

Buat array jawaban dengan panjang n.
Untuk setiap indeks i, tetapkan total = 0.
Tambahkan nums[j] ke total untuk setiap j dari 0 hingga i.
Simpan total pada indeks i di jawaban, lalu kembalikan jawaban setelah indeks terakhir.

def runningSum(nums):
    result = []
    for i in range(len(nums)):
        total = 0
        for j in range(i + 1):
            total += nums[j]
        result.append(total)
    return result

Catat jumlah total yang terus diperbarui

Intuisi

Jumlah i+1 angka pertama adalah jumlah i angka pertama ditambah nums[i]: result[i] = result[i-1] + nums[i]. Jadi, kamu tidak perlu melihat lebih jauh dari satu langkah ke belakang, dan satu variabel total sudah cukup. Untuk [3, 1, 4, 1, 5], hasilnya adalah 3, 4, 8, 9, 14, yang merupakan jawabannya.

Setiap elemen membutuhkan satu operasi penjumlahan: waktu O(n), dan ruang tambahan O(1) selain ruang untuk jawaban.

Algoritma

Buat array jawaban dengan panjang n dan tetapkan total = 0.
Telusuri indeks dari kiri ke kanan dan tambahkan nums[i] ke total.
Tulis total ke indeks i pada jawaban.
Kembalikan jawaban.

def runningSum(nums):
    result = []
    total = 0
    for num in nums:
        total += num
        result.append(total)
    return result

Jebakan dan kasus tepi

Mengatur ulang total di dalam perulangan. Setiap jawaban menjadi nums[i] saja, dan [3, 1, 4] kembali tanpa perubahan.
Membaca result[i-1] saat i = 0. Sebagian besar bahasa akan mengakses indeks di luar batas; Python membaca elemen terakhir, sehingga versi in place menambahkan angka terakhir ke angka pertama.
Menghentikan perulangan bagian dalam brute force pada j < i. Cara ini tidak menyertakan nums[i], sehingga setiap jawaban kurang satu angka.
Di R, menambahkan elemen ke jawaban dengan result <- c(result, total) menyalin vector di setiap langkah dan membuat pendekatan cepat menjadi kuadratik. Alokasikan panjang penuh terlebih dahulu.
Di C, lupa menulis *returnSize = numsSize. Pemanggil pun tidak tahu berapa banyak total yang harus dibaca.

Pertanyaan yang sering diajukan4

Apa jumlah kumulatif dari sebuah array?

Ini adalah array kedua yang setiap elemennya merupakan total dari semua elemen hingga dan termasuk posisi yang sama pada array pertama. Ini juga disebut jumlah awalan atau jumlah kumulatif. Jumlah berjalan dari [3, 1, 4, 1, 5] adalah [3, 4, 8, 9, 14].

Apa kompleksitas waktu untuk menghitung jumlah kumulatif?

Waktu O(n) dengan satu total yang dibawa dari kiri ke kanan, dan ruang tambahan O(1) selain jawaban. Menghitung ulang setiap prefiks dari awal membutuhkan O(n²).

Bisakah kamu menghitung jumlah kumulatif secara langsung?

Ya. Telusuri dari indeks 1 hingga akhir dan atur nums[i] += nums[i-1]. Saat itu, nums[i-1] sudah menyimpan total semua nilai hingga indeks tersebut, sehingga setiap elemen berakhir sebagai jumlah prefiksnya. Nilai aslinya akan hilang.

Bagaimana prefix sum membantu menjawab kueri jumlah rentang?

Jumlah slice nums[l..r] adalah prefix[r] - prefix[l-1], atau prefix[r] saat l = 0. Dengan [3, 4, 8, 9, 14], indeks 2 hingga 4 berjumlah 14 - 4 = 10. Setiap kueri membutuhkan O(1) setelah satu pemindaian O(n).

def runningSum(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [3, 1, 4, 1, 5]

Output yang diharapkan

[3, 4, 8, 9, 14]