Pattern · Prefix Sum (Tổng tiền tố)Trung bình
Đoạn Con Có Tổng Bằng KSubarray Sum Equals K
Hiểu bài
Cho mảng số nguyên nums (có thể chứa số âm) và số nguyên k. Đếm số đoạn con liên tiếp có tổng bằng k.
Ví dụ:
ts
nums = [1, 2, 3], k = 3
output = 2 // hai đoạn: [1, 2] và [3]
nums = [1, -1, 0], k = 0
output = 3 // [1, -1], [0], [1, -1, 0]Lưu ý ngay từ đầu: vì mảng có số âm, tổng của cửa sổ không đơn điệu khi mở rộng — Sliding Window co giãn cửa sổ dựa trên "tổng tăng khi thêm phần tử" nên không áp dụng được.
Đây là dấu hiệu chuyển sang prefix sum + Hash Map.
Cách cơ bản
O(n²) time · O(1) spacets
function subarraySum(nums: number[], k: number): number {
let count = 0
// xét mọi đoạn con [i..j]
for (let i = 0; i < nums.length; i++) {
let sum = 0
for (let j = i; j < nums.length; j++) {
sum += nums[j]
if (sum === k) count++
}
}
return count
}Vì sao cách này chậm:
Xét mọi cặp điểm đầu i, điểm cuối j — cộng dồn theo j nên mỗi đoạn tốn O(1), nhưng số đoạn là n(n+1)/2.
Với n = 2·10⁴ → khoảng 2·10⁸ bước, quá chậm.
Mở khoá để xem lời giải tối ưu, chạy thử từng bước và câu hỏi liên quan
Xem đầy đủ chạy thử từng bước, Big-O, trường hợp biên và biến thể công ty Việt Nam.