Running Sum of an Array

Q: Tổng lũy kế của một mảng là gì?

Đây là một mảng thứ hai, trong đó mỗi phần tử là tổng của mọi thứ tính đến và bao gồm vị trí tương ứng trong mảng thứ nhất. Nó còn được gọi là tổng tiền tố hoặc tổng tích lũy. Tổng lũy kế của [3, 1, 4, 1, 5] là [3, 4, 8, 9, 14] .

Q: Độ phức tạp thời gian khi tính tổng lũy kế là bao nhiêu?

Thời gian O(n) với một tổng được tính dồn từ trái sang phải, và dùng thêm O(1) bộ nhớ ngoài đáp án. Tính lại từng tiền tố từ đầu sẽ mất O(n²) .

Q: Bạn có thể tính tổng tích lũy ngay tại chỗ không?

Đúng vậy. Duyệt từ chỉ số 1 đến cuối mảng và gán nums[i] += nums[i-1] . Lúc đó, nums[i-1] đã chứa tổng của mọi phần tử tính đến vị trí đó, nên mỗi phần tử cuối cùng sẽ chứa tổng tiền tố của nó. Bạn sẽ mất các giá trị ban đầu.

Q: Làm thế nào tổng tiền tố giúp xử lý truy vấn tổng trên một khoảng?

Tổng của một lát cắt nums[l..r] là prefix[r] - prefix[l-1] , hoặc là prefix[r] khi l = 0 . Với [3, 4, 8, 9, 14] , các chỉ số từ 2 đến 4 có tổng là 14 - 4 = 10 . Sau một lượt duyệt O(n) , mỗi truy vấn chỉ mất O(1) .

Người mớiTổng tiền tố

+10

Bạn nhận được một mảng các số nguyên nums. Hãy trả về một mảng mới có cùng độ dài, trong đó phần tử tại chỉ số i là nums[0] + nums[1] + ... + nums[i], tức tổng của i+1 số đầu tiên.

Hàm

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

numsinteger-array: các số cần cộng từ trái sang phải
Trả vềinteger-array: tổng lũy kế, mỗi phần tử của nums có một tổng

Ràng buộc

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
Mọi tổng đang chạy đều nằm trong phạm vi số nguyên có dấu 32 bit.

Ví dụ

Đầu vào: nums = [3, 1, 4, 1, 5]
Đầu ra: [3, 4, 8, 9, 14]
Giải thích: Tiếp tục cộng: 3, rồi đến 3 + 1 = 4, 4 + 4 = 8, 8 + 1 = 9 và 9 + 5 = 14. Mỗi tổng được đưa vào chỉ số của số được cộng vào cuối cùng.

Đầu vào: nums = [-2, 5, -3]
Đầu ra: [-2, 3, 0]
Giải thích: Số âm làm giảm tổng: -2, rồi -2 + 5 = 3, rồi 3 + (-3) = 0.

Đầu vào: nums = [7]
Đầu ra: [7]
Giải thích: Một số duy nhất có tổng đang chạy chỉ gồm chính nó, nên đáp án là [7].

Câu hỏi mở rộng

Bạn có thể xây dựng cách tương tự cho một lưới, trong đó mỗi ô chứa tổng của hình chữ nhật từ góc trên bên trái đến ô đó không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Mỗi đáp án là tổng của một tiền tố (prefix) của nums, và các tiền tố liền kề chỉ khác nhau một phần tử. Tính lại từng tiền tố từ đầu sẽ lặp lại gần như toàn bộ công việc. Thay vào đó, hãy giữ lại một tổng rồi cập nhật nó, như vậy mỗi đáp án chỉ cần một phép cộng.

Cộng từng tiền tố từ đầu

Ý tưởng

Làm theo định nghĩa: với mỗi chỉ số i, đặt tổng bằng 0, cộng các giá trị từ nums[0] đến nums[i], rồi lưu lại. Cách này đúng vì mỗi kết quả được tính chính xác theo định nghĩa.

Chỉ số i cần i+1 phép cộng, nên mảng cần n(n+1)/2 phép cộng: khoảng 1.25 × 10^7 phép cộng với n = 5000, trong trường hợp này 5000 vẫn đáp ứng được.

Thuật toán

Tạo một mảng kết quả có độ dài n.
Với mỗi chỉ số i, đặt total = 0.
Cộng nums[j] vào total với mọi j từ 0 đến i.
Lưu total tại chỉ số i của mảng kết quả, rồi trả về mảng kết quả sau chỉ số cuối cùng.

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

Theo dõi tổng đang chạy

Ý tưởng

Tổng của i+1 số đầu tiên bằng tổng của i số đầu tiên cộng với nums[i]: result[i] = result[i-1] + nums[i]. Vì vậy, bạn không bao giờ cần xem lại quá một bước, và chỉ cần một biến total. Với [3, 1, 4, 1, 5], kết quả lần lượt là 3, 4, 8, 9, 14, đó chính là đáp án.

Mỗi phần tử cần một phép cộng: thời gian O(n) và bộ nhớ phụ O(1), không tính phần bộ nhớ dành cho đáp án.

Thuật toán

Tạo một mảng kết quả có độ dài n và đặt total = 0.
Duyệt các chỉ số từ trái sang phải và cộng nums[i] vào total.
Ghi total vào chỉ số i của mảng kết quả.
Trả về mảng kết quả.

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

Lỗi thường gặp và trường hợp biên

Đặt lại total bên trong vòng lặp. Mỗi đáp án chỉ còn là nums[i], và [3, 1, 4] được giữ nguyên.
Đọc result[i-1] tại i = 0. Hầu hết ngôn ngữ sẽ truy cập vượt phạm vi; Python đọc phần tử cuối cùng, nên phiên bản tại chỗ cộng số cuối cùng vào số đầu tiên.
Dừng vòng lặp bên trong của cách vét cạn tại j < i. Cách này bỏ sót nums[i], nên mỗi đáp án thiếu một số.
Trong R, thêm dần đáp án bằng result <- c(result, total) sẽ sao chép vector ở mỗi bước và khiến cách tiếp cận nhanh có độ phức tạp bậc hai. Hãy cấp phát trước toàn bộ độ dài.
Trong C, quên *returnSize = numsSize. Khi đó, bên gọi không biết cần đọc bao nhiêu tổng.

Câu hỏi thường gặp4

Tổng lũy kế của một mảng là gì?

Đây là một mảng thứ hai, trong đó mỗi phần tử là tổng của mọi thứ tính đến và bao gồm vị trí tương ứng trong mảng thứ nhất. Nó còn được gọi là tổng tiền tố hoặc tổng tích lũy. Tổng lũy kế của [3, 1, 4, 1, 5] là [3, 4, 8, 9, 14].

Độ phức tạp thời gian khi tính tổng lũy kế là bao nhiêu?

Thời gian O(n) với một tổng được tính dồn từ trái sang phải, và dùng thêm O(1) bộ nhớ ngoài đáp án. Tính lại từng tiền tố từ đầu sẽ mất O(n²).

Bạn có thể tính tổng tích lũy ngay tại chỗ không?

Đúng vậy. Duyệt từ chỉ số 1 đến cuối mảng và gán nums[i] += nums[i-1]. Lúc đó, nums[i-1] đã chứa tổng của mọi phần tử tính đến vị trí đó, nên mỗi phần tử cuối cùng sẽ chứa tổng tiền tố của nó. Bạn sẽ mất các giá trị ban đầu.

Làm thế nào tổng tiền tố giúp xử lý truy vấn tổng trên một khoảng?

Tổng của một lát cắt nums[l..r] là prefix[r] - prefix[l-1], hoặc là prefix[r] khi l = 0. Với [3, 4, 8, 9, 14], các chỉ số từ 2 đến 4 có tổng là 14 - 4 = 10. Sau một lượt duyệt O(n), mỗi truy vấn chỉ mất O(1).

def runningSum(nums):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

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

Đầu ra mong đợi

[3, 4, 8, 9, 14]