4Sum

Q: Độ phức tạp thời gian của 4Sum là bao nhiêu?

O(n³). Hai vòng lặp chọn khoảng n²/2 cặp (i, j) , và mỗi cặp được duyệt một lần bằng hai con trỏ với tối đa n bước; thao tác sắp xếp O(n log n) không đáng kể so với phần đó.

Q: Làm thế nào để tổng quát hóa 4Sum thành kSum?

Viết kSum(nums, target, k) trên một danh sách đã sắp xếp. Với k = 2, hàm này chạy lượt quét bằng hai con trỏ. Với k lớn hơn, hàm lặp qua giá trị đầu tiên, bỏ qua các giá trị lặp lại rồi gọi lại chính nó với k-1 và target - nums[i] trên các giá trị ở bên phải. Mỗi cấp độ làm tăng thêm một thừa số n, vì vậy kSum có độ phức tạp O(n^(k-1)).

Q: Có thể giải bài toán 4Sum trong O(n²) không?

Bạn có thể nhóm các tổng của từng cặp trong một bảng băm, rồi ghép mỗi cặp với các cặp có tổng bằng target trừ đi tổng của cặp đó. Cách này nhanh khi ít cặp có cùng tổng, nhưng một tổng có thể chứa O(n²) cặp, nên trong trường hợp xấu nhất, độ phức tạp cũng không tốt hơn O(n³).

Trung bìnhHai con trỏ Sắp xếp

+10

Bạn nhận được một danh sách (list) số nguyên (integer) nums và một số nguyên target. Hãy trả về mọi bộ bốn [a, b, c, d] sao cho bốn giá trị của chúng nằm ở bốn vị trí khác nhau trong nums và có tổng bằng target. Viết các giá trị trong mỗi bộ bốn theo thứ tự không giảm. Nếu có thể chọn cùng bốn giá trị từ những vị trí khác nhau, bộ bốn đó vẫn chỉ xuất hiện một lần. Sắp xếp kết quả theo giá trị thứ nhất, rồi đến giá trị thứ hai, rồi đến giá trị thứ ba. Nếu không có bộ bốn nào thỏa mãn, hãy trả về một danh sách rỗng.

Hàm

fourSum(nums: integer-array, target: integer) → integer-2d-array

numsinteger-array: các số để chọn, ít nhất một số
targetinteger: tổng mà mỗi bộ bốn phần tử phải đạt được
Trả vềinteger-2d-array: các bộ bốn phần tử phân biệt có tổng bằng target, mỗi bộ đều được sắp xếp, danh sách cũng được sắp xếp; một danh sách rỗng nếu không có bộ nào

Ràng buộc

1 ≤ nums.length ≤ 200
-10⁸ ≤ nums[i] ≤ 10⁸
-10⁹ ≤ target ≤ 10⁹
Tổng của bất kỳ bốn giá trị nào nằm trong khoảng từ -4 × 10⁸ đến 4 × 10⁸, nên có thể lưu trong một số nguyên 32 bit.
Các bộ bốn chứa cùng bốn giá trị được tính là một.

Ví dụ

Đầu vào: nums = [3, -1, 0, 2, -2, 1, -3]target = 1
Đầu ra: [[-3, -1, 2, 3], [-3, 0, 1, 3], [-2, -1, 1, 3], [-2, 0, 1, 2]]
Giải thích: Mỗi bộ bốn số đều có tổng bằng 1, ví dụ -3 + (-1) + 2 + 3. Hai bộ bắt đầu bằng -3 đứng trước, được sắp xếp theo giá trị thứ hai: -1 trước 0.

Đầu vào: nums = [4, 4, 4, 4, 4, 4]target = 16
Đầu ra: [[4, 4, 4, 4]]
Giải thích: Cả 15 cách chọn 4 vị trí trong số 6 vị trí đều cho ra bốn số 4 có tổng bằng 16, vì vậy [4, 4, 4, 4] xuất hiện một lần.

Đầu vào: nums = [1, 5, 2, 9]target = 3
Đầu ra: []
Giải thích: Lựa chọn duy nhất là cả bốn số, và 1 + 5 + 2 + 9 = 17, không phải 3, nên đáp án là một danh sách rỗng.

Câu hỏi mở rộng

Đếm số nhóm gồm bốn vị trí có tổng giá trị bằng target, thay vì đếm các bộ bốn giá trị phân biệt. Ví dụ thứ hai có 15 nhóm. Bạn có thể giải bài này trong O(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

Kiểm tra mọi nhóm gồm bốn vị trí tốn O(n⁴), và các giá trị lặp lại khiến cùng một bộ bốn phần tử được tạo ra nhiều lần. Áp dụng cách rút gọn của 3Sum sâu thêm một cấp: sắp xếp, cố định hai giá trị đầu tiên bằng hai vòng lặp, tìm cặp cuối cùng bằng hai con trỏ và bỏ qua các giá trị lặp lại ở mọi cấp.

Thử mọi nhóm gồm bốn

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

Ý tưởng

Trước tiên, hãy sắp xếp để các vị trí i < j < k < l chứa giá trị theo thứ tự không giảm và mỗi bộ bốn phần tử được viết đúng thứ tự. Bốn vòng lặp lồng nhau sẽ duyệt mọi cách chọn bốn vị trí. Để tránh lặp lại, một vòng lặp chuyển sang vị trí tiếp theo khi giá trị ở đó giống với giá trị mà nó đã thử ở bước trước. Với sáu số 4, mỗi vòng lặp chỉ thử vị trí đầu tiên, nên [4, 4, 4, 4] chỉ xuất hiện một lần thay vì 15 lần.

Với 200 số, có 64,684,950 bộ gồm bốn số, và số lượng tăng khoảng 16 lần khi n tăng gấp đôi.

Thuật toán

Sắp xếp nums.
Lồng bốn vòng lặp với điều kiện i < j < k < l, mỗi vòng bắt đầu tại vị trí ngay sau vòng bao quanh nó.
Trong mỗi vòng lặp, bỏ qua vị trí không phải vị trí đầu tiên của vòng và có cùng giá trị với vị trí đứng trước.
Ghi lại [nums[i], nums[j], nums[k], nums[l]] khi tổng của bốn giá trị bằng target. Các vòng lặp tạo ra chúng theo thứ tự đã sắp xếp.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 2):
            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 - 1):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                for l in range(k + 1, n):
                    if l > k + 1 and nums[l] == nums[l - 1]:
                        continue  # same fourth value as the round before
                    if nums[i] + nums[j] + nums[k] + nums[l] == target:
                        quads.append([nums[i], nums[j], nums[k], nums[l]])
    return quads

Sắp xếp, hai vòng lặp, hai con trỏ

Ý tưởng

Cố định nums[i] và nums[j], phần còn lại là bài toán tìm một cặp: tìm hai giá trị ở bên phải j có tổng bằng target - nums[i] - nums[j]. Với một danh sách đã sắp xếp, chỉ cần duyệt một lượt là tìm được đáp án. Đặt lo ở j+1 và hi ở chỉ số cuối cùng. Nếu tổng nhỏ hơn target, dịch lo sang phải; nếu tổng lớn hơn, dịch hi sang trái.

Mỗi lần dịch sẽ loại bỏ một giá trị không thể góp mặt trong đáp án. Nếu tổng quá nhỏ, ngay cả giá trị lớn nhất còn lại, nums[hi], cũng không đủ để cộng với nums[lo], nên có thể loại bỏ nums[lo]. Nếu tổng quá lớn, có thể loại bỏ nums[hi] vì lý do ngược lại. Một cặp (i, j) cần tối đa n lần dịch, vì vậy n²/2 cặp có độ phức tạp O(n³).

Ở ví dụ đầu tiên, khi i ở vị trí -3 và j ở vị trí -1, lo dịch từ 0, qua 1 rồi đến 2, tại đó -3 + (-1) + 2 + 3 = 1.

Thuật toán

Sắp xếp nums.
Với mỗi i, bỏ qua nếu i > 0 và nums[i] bằng nums[i-1].
Với mỗi j đứng sau i, bỏ qua nếu j > i+1 và nums[j] bằng nums[j-1].
Đặt lo = j+1 và hi = n-1. Khi lo < hi, so sánh tổng của bốn giá trị với target: nếu nhỏ hơn thì dịch lo sang phải, nếu lớn hơn thì dịch hi sang trái.
Nếu khớp, ghi lại bộ bốn, dịch chuyển cả hai con trỏ, rồi tăng lo khi nó vẫn giữ giá trị vừa dùng.

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # this second value was already handled
            lo, hi = j + 1, n - 1
            while lo < hi:
                total = nums[i] + nums[j] + nums[lo] + nums[hi]
                if total < target:
                    lo += 1
                elif total > target:
                    hi -= 1
                else:
                    quads.append([nums[i], nums[j], nums[lo], nums[hi]])
                    lo += 1
                    hi -= 1
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1
    return quads

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

Bỏ qua j mỗi khi nums[j] bằng nums[j-1]. Tại j = i+1, điều này so sánh với giá trị mà i dùng, nên [2, 2, 2, 2, 2] với target 8 sẽ làm mất [2, 2, 2, 2].
Sao chép điều kiện thoát sớm của 3Sum nums[i] > target. Với [-5, -4, -3, -2, -1] và target -10, vòng lặp dừng ở -5 và bỏ sót [-4, -3, -2, -1].
Danh sách ngắn hơn bốn phần tử. Với một hoặc hai số, n-3 là số âm: 0..<(n - 3) gây lỗi trong Swift, còn n - 3 trên usize của Rust bị tràn số xuống dưới. Trước tiên, hãy trả về một danh sách rỗng.
Thu thập các bộ bốn phần tử trong một tập hợp băm rồi trả về chúng mà không sắp xếp.

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

Độ phức tạp thời gian của 4Sum là bao nhiêu?

O(n³). Hai vòng lặp chọn khoảng n²/2 cặp (i, j), và mỗi cặp được duyệt một lần bằng hai con trỏ với tối đa n bước; thao tác sắp xếp O(n log n) không đáng kể so với phần đó.

Làm thế nào để tổng quát hóa 4Sum thành kSum?

Viết kSum(nums, target, k) trên một danh sách đã sắp xếp. Với k = 2, hàm này chạy lượt quét bằng hai con trỏ. Với k lớn hơn, hàm lặp qua giá trị đầu tiên, bỏ qua các giá trị lặp lại rồi gọi lại chính nó với k-1 và target - nums[i] trên các giá trị ở bên phải. Mỗi cấp độ làm tăng thêm một thừa số n, vì vậy kSum có độ phức tạp O(n^(k-1)).

Có thể giải bài toán 4Sum trong O(n²) không?

Bạn có thể nhóm các tổng của từng cặp trong một bảng băm, rồi ghép mỗi cặp với các cặp có tổng bằng target trừ đi tổng của cặp đó. Cách này nhanh khi ít cặp có cùng tổng, nhưng một tổng có thể chứa O(n²) cặp, nên trong trường hợp xấu nhất, độ phức tạp cũng không tốt hơn O(n³).

def fourSum(nums, target):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

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

Đầu ra mong đợi

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