Pattern · Prefix Sum (Tổng tiền tố)Trung bình
Tích Mảng Ngoại Trừ Chính NóProduct of Array Except Self
Hiểu bài
Cho mảng số nguyên nums. Trả về mảng result sao cho result[i] bằng tích của tất cả phần tử trừ nums[i].
Ràng buộc quan trọng: không được dùng phép chia, và thuật toán phải chạy trong O(n).
Ví dụ:
ts
nums = [1, 2, 3, 4]
output = [24, 12, 8, 6]
// result[0] = 2·3·4 = 24, result[1] = 1·3·4 = 12, ...Cấm phép chia vì lý do thực tế: mảng có thể chứa số 0, và phép chia cho 0 không xác định.
Đây là bài áp dụng tư duy tiền tố nhưng thay phép cộng bằng phép nhân.
Cách cơ bản
O(n²) time · O(1) space thêm (không tính mảng kết quả)ts
function productExceptSelf(nums: number[]): number[] {
const n = nums.length
const result: number[] = []
for (let i = 0; i < n; i++) {
let product = 1
// nhân tất cả phần tử trừ vị trí i
for (let j = 0; j < n; j++) {
if (j !== i) product *= nums[j]
}
result.push(product)
}
return result
}Vì sao cách này chậm:
Với mỗi vị trí i phải quét lại toàn mảng để nhân n−1 phần tử còn lại.
Hai vòng lặp lồng nhau → O(n²), vượt giới hạn khi n cỡ 10⁵.
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.