3Sum

+10

Bạn nhận được một danh sách số nguyên nums. Hãy tìm mọi bộ ba [a, b, c] gồm các giá trị lấy từ ba vị trí khác nhau trong nums, sao cho a + b + c = 0. Viết mỗi bộ ba theo thứ tự không giảm (a ≤ b ≤ c) và chỉ liệt kê mỗi bộ ba phân biệt một lần, ngay cả khi có nhiều cách chọn vị trí tạo ra bộ ba đó. Trả về các bộ ba đã sắp xếp theo giá trị đầu tiên, rồi đến giá trị thứ hai.

Hàm

threeSum(nums: integer-array) → integer-2d-array

numsinteger-array: danh sách số nguyên, có ít nhất ba phần tử
Trả vềinteger-2d-array: mọi bộ ba riêng biệt có tổng bằng 0, mỗi bộ được sắp xếp theo thứ tự không giảm, danh sách được sắp xếp

Ràng buộc

3 ≤ nums.length ≤ 3000
-10⁵ ≤ nums[i] ≤ 10⁵
Ít nhất một bộ ba có tổng bằng 0.
Hai bộ ba giống nhau khi chúng chứa cùng ba giá trị.

Ví dụ

Đầu vào: nums = [-2, 0, 1, 1, -1, 2]
Đầu ra: [[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]
Giải thích: Ba bộ ba có tổng bằng 0. [-2, 1, 1] dùng giá trị 1 hai lần vì số 1 nằm ở hai vị trí; [-1, 0, 1] có thể dùng một trong hai số 1 nhưng chỉ xuất hiện một lần.

Đầu vào: nums = [0, 0, 0, 0]
Đầu ra: [[0, 0, 0]]
Giải thích: Bất kỳ ba số 0 nào trong bốn số cũng có tổng bằng 0. Có bốn cách chọn vị trí, nhưng tất cả đều cho ra cùng một bộ ba, nên đáp án chỉ tính [0, 0, 0] một lần.

Câu hỏi mở rộng

Mẫu tương tự giải được bài toán 4Sum: cố định hai giá trị rồi dùng hai con trỏ cho phần còn lại. Bạn có thể viết lời giải với độ phức tạp O(n³) và xử lý đúng các giá trị trùng lặp ở mọi cấp 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

Kiểm tra mọi bộ ba tốn O(n³), và mỗi bộ ba phải xuất hiện một lần, kể cả khi các giá trị lặp lại. Sắp xếp giải quyết cả hai vấn đề: các giá trị bằng nhau nằm cạnh nhau, nên bạn bỏ qua phần tử lặp bằng cách so sánh các phần tử liền kề; khi cố định giá trị nhỏ nhất, hai giá trị còn lại tạo thành bài toán tìm cặp có tổng cho một danh sách đã sắp xếp.

Thử mọi bộ ba

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Sắp xếp danh sách, rồi thử mọi bộ ba vị trí i < j < k. Các giá trị xuất hiện theo thứ tự, nên bạn có thể viết bộ ba đúng ngay khi tìm thấy, và các vòng lặp lồng nhau không bỏ sót trường hợp nào. Mỗi vòng lặp bỏ qua một vị trí có giá trị bằng giá trị mà chính vòng lặp đó đã thử trước đó, nên mỗi bộ ba phân biệt chỉ xuất hiện một lần. [-2, 1, 1] vẫn dùng cả hai số 1, vì việc bỏ qua chỉ so sánh bên trong một vòng lặp.

Có khoảng n³/6 bộ ba: n = 3000 nghĩa là 4.5 × 10^9 phép tính tổng.

Thuật toán

Sắp xếp nums.
Lặp qua i, sau đó lặp qua j bắt đầu từ i+1, rồi lặp qua k bắt đầu từ j+1. Trong mỗi vòng lặp, bỏ qua vị trí có giá trị bằng giá trị mà vòng lặp đó đã thử trước đó.
Ghi lại [nums[i], nums[j], nums[k]] khi tổng của ba giá trị bằng 0, rồi trả về các bộ ba theo thứ tự tìm được.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 1):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # same second value as the round before
            for k in range(j + 1, n):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                if nums[i] + nums[j] + nums[k] == 0:
                    triplets.append([nums[i], nums[j], nums[k]])
    return triplets

Sửa một giá trị, tìm cặp bằng tập hợp băm

Ý tưởng

Khi cố định nums[i], bạn cần hai giá trị đứng sau có tổng bằng -nums[i]: bài toán Two Sum. Duyệt j về bên phải của i, dùng một tập hợp để lưu các giá trị đã đi qua. Nếu need = -nums[i] - nums[j] nằm trong tập hợp, thì [nums[i], need, nums[j]] có tổng bằng 0. Với mỗi i, thao tác này mất trung bình O(n), nên toàn bộ quá trình tìm kiếm mất O(n²).

Sau khi tìm được một bộ ba, đưa j qua các bản sao của nums[j]: khi giá trị thứ nhất và thứ ba đã cố định, giá trị ở giữa cũng cố định. need xuất phát từ một vị trí đứng trước trong mảng đã sắp xếp, nên bộ ba có thứ tự, nhưng khi j di chuyển sang phải, need giảm dần: với một i, ta tìm được [-2, 1, 1] trước [-2, 0, 2]. Đảo ngược thứ tự từng nhóm trước khi thêm vào.

Thuật toán

Sắp xếp nums.
Với mỗi i, dừng lại khi nums[i] > 0 và bỏ qua i khi nums[i] bằng nums[i-1].
Bắt đầu với một tập hợp rỗng. Với mỗi j bắt đầu từ i+1, tính need = -nums[i] - nums[j]. Nếu need có trong tập hợp, ghi lại [nums[i], need, nums[j]] và chuyển j qua các bản sao của nums[j].
Thêm nums[j] vào tập hợp và chuyển sang j tiếp theo.
Đảo ngược các bộ ba tìm được với i này và nối chúng vào kết quả.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        group = []
        seen = set()  # values between position i and position j
        j = i + 1
        while j < n:
            need = -nums[i] - nums[j]
            if need in seen:
                group.append([nums[i], need, nums[j]])
                while j + 1 < n and nums[j + 1] == nums[j]:
                    j += 1
            seen.add(nums[j])
            j += 1
        # need shrinks as nums[j] grows, so this group came out backwards
        group.reverse()
        triplets.extend(group)
    return triplets

Sắp xếp và sử dụng hai con trỏ

Ý tưởng

Cố định nums[i], đặt lo tại i+1 và hi tại chỉ số cuối cùng. Nếu tổng nhỏ hơn 0, nums[lo] vẫn chưa đủ lớn ngay cả khi ghép với giá trị lớn nhất còn lại là nums[hi], nên nó không thể ghép với bất kỳ giá trị nào trong phạm vi hiện tại: dịch lo sang phải. Trường hợp tổng lớn hơn 0 thì ngược lại: nums[hi] quá lớn ngay cả khi ghép với giá trị nhỏ nhất còn lại, nên dịch hi sang trái. Mỗi bước loại bỏ hẳn một giá trị mà không bỏ sót bộ ba nào, vì vậy một giá trị i tốn nhiều nhất n bước và việc tìm kiếm có độ phức tạp O(n²), không cần thêm bộ nhớ.

Các giá trị lặp lại cần hai quy tắc. Bỏ qua i nếu giá trị của nó bằng giá trị đứng ngay trước. Sau khi tìm thấy một kết quả khớp, dịch lo qua các bản sao của giá trị đó. Không cần quy tắc cho hi: một bản sao của nums[hi] cũ giờ sẽ tạo ra tổng lớn hơn 0 và tự dịch ra xa. Vì i lần lượt xét các giá trị phân biệt theo thứ tự tăng dần, còn lo chỉ dịch sang phải, các bộ ba sẽ được tạo theo thứ tự đã sắp xếp.

Thuật toán

Sắp xếp nums.
Với mỗi i, dừng khi nums[i] > 0 và bỏ qua i khi nums[i] bằng nums[i-1].
Đặt lo = i+1 và hi = n-1. Khi lo < hi, cộng nums[i], nums[lo] và nums[hi].
Nếu tổng nhỏ hơn 0, dịch lo sang phải. Nếu tổng lớn hơn 0, dịch hi sang trái.
Nếu tổng bằng 0, ghi lại bộ ba, dịch cả hai con trỏ, rồi dịch lo qua các bản sao của giá trị nó vừa dùng.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        lo, hi = i + 1, n - 1
        while lo < hi:
            total = nums[i] + nums[lo] + nums[hi]
            if total < 0:
                lo += 1
            elif total > 0:
                hi -= 1
            else:
                triplets.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
    return triplets

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

Bỏ qua i khi nums[i] bằng nums[i+1]. Trong [-1, -1, 2], bạn sẽ bỏ sót [-1, -1, 2]; hãy so sánh với nums[i-1].
Dừng khi nums[i] ≥ 0 thay vì nums[i] > 0. Cách này bỏ sót [0, 0, 0].
Xóa các phần tử lặp lại ở cuối. Với 3000 số 0, vòng lặp ghi nhận hàng triệu bản sao của [0, 0, 0] trước khi có bước dọn dẹp.
Dùng cùng một vị trí hai lần. Phiên bản dùng tập hợp băm, khi thêm toàn bộ danh sách vào tập hợp ngay từ đầu, sẽ biến [-2, 1, 3] thành [-2, 1, 1].
Quên đảo ngược từng nhóm trong phiên bản dùng tập hợp băm. Các bộ ba phải được sắp xếp.

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

Độ phức tạp thời gian của 3Sum là gì?

Lời giải sắp xếp và dùng hai con trỏ chạy trong thời gian O(n²): việc sắp xếp tốn O(n log n), và mỗi trong số n lựa chọn giá trị đầu tiên cần một lượt duyệt O(n). Lời giải cần O(1) bộ nhớ bổ sung, không tính phần sắp xếp và đầu ra. Kiểm tra mọi bộ ba tốn O(n³).

Tôi nên dùng hai con trỏ hay tập hợp băm cho bài toán 3Sum?

Cả hai đều chạy trong thời gian O(n²). Hai con trỏ không cần thêm bộ nhớ và trả về các bộ ba theo đúng thứ tự. Tập hợp băm tốn O(n) bộ nhớ, đồng thời cần cẩn thận để giữ các vị trí riêng biệt và sắp xếp đầu ra. Ý tưởng dùng tập hợp băm hữu ích khi bạn không thể sắp xếp, như trong bài Two Sum, nơi bạn trả về các chỉ số ban đầu.

Có thể giải bài toán 3Sum nhanh hơn O(n²) không?

Không chênh lệch nhiều. Những thuật toán tốt nhất đã biết chỉ nhanh hơn n² một vài thừa số logarit, và nhiều kết quả về độ khó trong hình học tính toán giả định rằng không có thuật toán nào đạt được lũy thừa của n nhỏ hơn 2. O(n²) là đáp án mà các buổi phỏng vấn mong đợi.

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

Kiểm thử #1

Kiểm thử #2

Đối số

nums = [-2, 0, 1, 1, -1, 2]

Đầu ra mong đợi

[[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]

3Sum

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Thử mọi bộ ba

Sửa một giá trị, tìm cặp bằng tập hợp băm

Sắp xếp và sử dụng hai con trỏ

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

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

Bài tập tương tự