Pattern · Hai con trỏTrung bình
Ba Tổng Bằng Không3Sum
Hiểu bài
Cho mảng số nguyên nums, tìm tất cả bộ ba phần tử phân biệt theo chỉ số [i, j, k] sao cho nums[i] + nums[j] + nums[k] === 0. Kết quả không được chứa bộ ba trùng lặp.
Ví dụ:
ts
nums = [-1, 0, 1, 2, -1, -4]
output = [[-1, -1, 2], [-1, 0, 1]]
// Hai bộ ba hợp lệ — không có bộ trùng
nums = [0, 1, 1]
output = [] // không có bộ nào cộng ra 0
nums = [0, 0, 0]
output = [[0, 0, 0]]"Phân biệt theo chỉ số" nghĩa là cùng một giá trị ở hai vị trí khác nhau vẫn dùng được — nhưng cùng một bộ ba giá trị thì không được trả ra hai lần.
Cách cơ bản
O(n³) time, O(n) spacets
function threeSum(nums: number[]): number[][] {
const result: number[][] = []
const seen = new Set<string>()
for (let i = 0; i < nums.length - 2; i++) {
for (let j = i + 1; j < nums.length - 1; j++) {
for (let k = j + 1; k < nums.length; k++) {
if (nums[i] + nums[j] + nums[k] === 0) {
const triple = [nums[i], nums[j], nums[k]].sort((a, b) => a - b)
const key = triple.join(',')
if (!seen.has(key)) { seen.add(key); result.push(triple) }
}
}
}
}
return result
}Vì sao cách này chậm:
Ba vòng lặp lồng nhau kiểm tra mọi bộ ba.
- Với n=3000 → 27·10⁹ phép tính — hoàn toàn vượt giới hạn.
- Cần giảm xuống ít nhất O(n²).
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.