Minimum Size Subarray Sum

Q: Độ phức tạp thời gian của bài toán tổng mảng con có kích thước tối thiểu là bao nhiêu?

Cửa sổ trượt chạy trong thời gian O(n) và dùng O(1) bộ nhớ. Vòng lặp bên trong trông có vẻ mất thời gian bậc hai, nhưng left chỉ di chuyển về phía trước, nên nó tiến lên nhiều nhất n lần trong toàn bộ quá trình chạy. Phiên bản dùng tổng tiền tố có độ phức tạp O(n log n) , còn thử mọi vị trí bắt đầu có độ phức tạp O(n²) .

Q: Tại sao cửa sổ trượt cần các số dương?

Cửa sổ chỉ thu hẹp khi tổng của nó đạt đến target , vì lúc đó việc bỏ một giá trị chỉ có thể làm tổng giảm xuống. Nếu giá trị bị bỏ là số âm, tổng sẽ tăng lên. Với [5, -10, 20] và target = 15 , cửa sổ dừng ở -10, 20 với tổng là 10 và không bao giờ đo [20] , có độ dài 1.

Q: Tại sao cần học lời giải tổng tiền tố O(n log n) nếu đã có O(n)?

Người phỏng vấn thường hỏi đến cách này sau câu trả lời O(n) . Cách này tận dụng tính dương theo một cách khác: các tổng tiền tố đã được sắp xếp, nên tìm kiếm nhị phân sẽ xác định vị trí đầu tiên mà tổng đang chạy vượt qua ngưỡng. Công cụ tương tự chọn ngẫu nhiên một chỉ số theo tỷ lệ với trọng số của nó.

Q: Subarray có phải có tổng bằng chính xác target không?

Không. Mọi tổng lớn hơn hoặc bằng target đều được tính. Với target = 15 , cửa sổ gồm 9, 3, 7 có tổng là 19 và vẫn có độ dài 3.

Trung bìnhCửa sổ trượt Tổng tiền tố

+10

Bạn nhận được một số nguyên dương target và một mảng nums gồm các số nguyên dương. Hãy tìm mảng con ngắn nhất (một dãy gồm các phần tử liền kề) có tổng ít nhất bằng target, rồi trả về độ dài của nó. Nếu không có mảng con nào đạt đến target, hãy trả về 0.

Hàm

minSubArrayLen(target: integer, nums: integer-array) → integer

targetinteger: tổng mà một mảng con phải đạt hoặc vượt qua
numsinteger-array: mảng số nguyên dương
Trả vềinteger: Độ dài của mảng con ngắn nhất có tổng ít nhất bằng target, hoặc 0 nếu không có mảng nào như vậy

Ràng buộc

1 ≤ target ≤ 10⁹
1 ≤ nums.length ≤ 2 × 10⁴
1 ≤ nums[i] ≤ 10⁴

Ví dụ

Đầu vào: target = 15nums = [4, 2, 9, 3, 7, 1, 5]
Đầu ra: 3
Giải thích: Không có hai phần tử liền kề nào đạt 15: cặp lớn nhất là 9 + 3 = 12. Có ba phần tử đạt mức đó: 4 + 2 + 9 = 15 và 9 + 3 + 7 = 19, vậy đáp án là 3.

Câu hỏi mở rộng

Nếu nums cũng có thể chứa số 0 và số âm, khiến cửa sổ trượt không còn hiệu quả, bạn sẽ giải bài toán này như thế nào?

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

Mọi giá trị đều dương, vì vậy mở rộng mảng con sẽ làm tăng tổng, còn cắt bớt sẽ làm giảm tổng. Do đó, khi điểm bắt đầu dịch sang phải, điểm kết thúc tốt nhất không bao giờ dịch sang trái. Chỉ cần dùng một cửa sổ tăng về bên phải và thu hẹp về bên trái để tìm đáp án trong một lượt duyệt.

Mở rộng từ mọi điểm bắt đầu

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

Ý tưởng

Cố định điểm bắt đầu rồi cộng các giá trị về phía bên phải. Lần đầu tiên tổng đang tính đạt đến target, bạn có mảng con ngắn nhất bắt đầu từ vị trí đó, vì mọi mảng con ngắn hơn đều có tổng nhỏ hơn. Ghi lại độ dài của nó rồi chuyển sang điểm bắt đầu tiếp theo; đáp án là độ dài nhỏ nhất trong tất cả các điểm bắt đầu.

Khi không có mảng con nào đạt đến giá trị mục tiêu, mỗi điểm bắt đầu đều phải duyệt đến cuối mảng: n(n+1)/2 phép cộng, khoảng 2 × 10^8 khi n = 2 × 10^4.

Thuật toán

Đặt best bằng 0, nghĩa là chưa tìm thấy gì.
Với mỗi chỉ số bắt đầu, đặt tổng đang tính bằng 0.
Di chuyển chỉ số kết thúc sang phải từ vị trí bắt đầu, cộng nums[end] vào tổng.
Khi tổng đạt đến target, giữ lại end-start+1 nếu giá trị này nhỏ hơn best, rồi dừng mở rộng từ vị trí bắt đầu này.
Trả về best.

def minSubArrayLen(target, nums):
    n = len(nums)
    best = 0  # 0 means no subarray found yet
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            if total >= target:
                # The shortest subarray from this start ends here
                if best == 0 or end - start + 1 < best:
                    best = end - start + 1
                break
    return best

Tổng tiền tố và tìm kiếm nhị phân

Ý tưởng

Gọi prefix[k] là tổng của k giá trị đầu tiên, với prefix[0] = 0. Tổng của nums[start..end-1] là prefix[end] - prefix[start], vì vậy với một điểm bắt đầu cố định, bạn cần tìm end nhỏ nhất sao cho prefix[end] ≥ prefix[start] + target. Các giá trị dương khiến prefix tăng nghiêm ngặt, nên tìm kiếm nhị phân sẽ tìm được điểm kết thúc đó.

Trong ví dụ đầu tiên, prefix là [0, 4, 6, 15, 18, 25, 26, 31]. Với điểm bắt đầu 2, bạn cần 6 + 15 = 21. Giá trị prefix đầu tiên lớn hơn hoặc bằng 21 là 25 tại chỉ số 5, nên cửa sổ gồm 9, 3, 7, có độ dài 3.

Nếu prefix[n] nhỏ hơn giá trị cần có tại một điểm bắt đầu, thì không điểm bắt đầu nào về sau thỏa mãn, vì vậy bạn dừng lại. Có n lần tìm kiếm nhị phân: thời gian O(n log n) và bộ nhớ O(n).

Thuật toán

Tạo prefix có độ dài n+1, với prefix[k+1] = prefix[k] + nums[k].
Với mỗi vị trí bắt đầu, tính need = prefix[start] + target.
Nếu prefix[n] < need, dừng lại: không có vị trí bắt đầu nào phía sau có thể thỏa mãn.
Tìm kiếm nhị phân các vị trí từ start+1 đến n để tìm end đầu tiên sao cho prefix[end] ≥ need, rồi giữ lại end-start nếu đó là độ dài ngắn nhất tính đến lúc này.
Trả về độ dài ngắn nhất, hoặc 0 nếu không có vị trí bắt đầu nào thỏa mãn.

from bisect import bisect_left


def minSubArrayLen(target, nums):
    n = len(nums)
    # prefix[k] is the sum of the first k values; it only grows
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    best = 0
    for start in range(n):
        need = prefix[start] + target
        if prefix[n] < need:
            break  # no window from here on can reach target
        # The first end with prefix[end] >= need closes the shortest window
        end = bisect_left(prefix, need, start + 1)
        if best == 0 or end - start < best:
            best = end - start
    return best

Cửa sổ trượt

Ý tưởng

Bạn có thể an toàn bỏ hẳn một điểm bắt đầu. Khi cửa sổ nums[left..right] lần đầu đạt đến target, cửa sổ kết thúc tại right-1 chưa đạt đến mức đó, nếu không vòng lặp đã thu hẹp cửa sổ sớm hơn một bước. Vì vậy, right là điểm kết thúc sớm nhất cho điểm bắt đầu này, còn các điểm kết thúc về sau chỉ tạo ra mảng con dài hơn. Ghi lại độ dài, bỏ nums[left], rồi tiếp tục thu hẹp khi tổng vẫn đạt đến target.

Trong ví dụ đầu tiên, tổng tăng lần lượt thành 4, 6, 15: ghi lại 3 rồi bỏ 4. Cộng thêm 3 và 7 thì được 21: ghi lại 4, bỏ 2 (còn 19), ghi lại 3, bỏ 9 (còn 10). Những kết quả về sau không có kết quả nào tốt hơn 3.

Mỗi chỉ số đi vào cửa sổ một lần và rời khỏi cửa sổ một lần, vì vậy các vòng lặp lồng nhau thực hiện tổng cộng O(n) thao tác, với không gian O(1).

Thuật toán

Đặt left = 0, total = 0 và best = 0.
Với mỗi right, cộng nums[right] vào total.
Trong khi total ≥ target, giữ lại right-left+1 nếu giá trị này lớn hơn best, trừ nums[left] rồi dịch left sang phải một bước.
Trả về best, giá trị này vẫn là 0 nếu tổng chưa bao giờ đạt target.

def minSubArrayLen(target, nums):
    best = 0  # 0 means no window found yet
    total = 0  # sum of nums[left .. right]
    left = 0
    for right in range(len(nums)):
        total += nums[right]
        # Shrink while the window still reaches target
        while total >= target:
            if best == 0 or right - left + 1 < best:
                best = right - left + 1
            total -= nums[left]
            left += 1
    return best

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

Thu nhỏ cửa sổ bằng if thay vì while. Với target = 12 và [1, 1, 2, 3, 12], thêm 12 khiến tổng bằng 19; if ghi nhận độ dài 5, xóa một giá trị rồi tiếp tục, vì vậy cửa sổ [12] không bao giờ được đo.
Ghi nhận độ dài sau khi xóa nums[left]. Bạn phải đo cửa sổ có tổng đạt target.
So sánh bằng > thay vì ≥. Với [3, 3, 3] và target = 9, đáp án là 3, không phải 0.
Trả về giá trị canh gác. Nếu best bắt đầu bằng n+1 hoặc vô cực, hãy trả về 0 khi không có cửa sổ nào đạt target, như trong ví dụ thứ hai.

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

Độ phức tạp thời gian của bài toán tổng mảng con có kích thước tối thiểu là bao nhiêu?

Cửa sổ trượt chạy trong thời gian O(n) và dùng O(1) bộ nhớ. Vòng lặp bên trong trông có vẻ mất thời gian bậc hai, nhưng left chỉ di chuyển về phía trước, nên nó tiến lên nhiều nhất n lần trong toàn bộ quá trình chạy. Phiên bản dùng tổng tiền tố có độ phức tạp O(n log n), còn thử mọi vị trí bắt đầu có độ phức tạp O(n²).

Tại sao cửa sổ trượt cần các số dương?

Cửa sổ chỉ thu hẹp khi tổng của nó đạt đến target, vì lúc đó việc bỏ một giá trị chỉ có thể làm tổng giảm xuống. Nếu giá trị bị bỏ là số âm, tổng sẽ tăng lên. Với [5, -10, 20] và target = 15, cửa sổ dừng ở -10, 20 với tổng là 10 và không bao giờ đo [20], có độ dài 1.

Tại sao cần học lời giải tổng tiền tố O(n log n) nếu đã có O(n)?

Người phỏng vấn thường hỏi đến cách này sau câu trả lời O(n). Cách này tận dụng tính dương theo một cách khác: các tổng tiền tố đã được sắp xếp, nên tìm kiếm nhị phân sẽ xác định vị trí đầu tiên mà tổng đang chạy vượt qua ngưỡng. Công cụ tương tự chọn ngẫu nhiên một chỉ số theo tỷ lệ với trọng số của nó.

Subarray có phải có tổng bằng chính xác target không?

Không. Mọi tổng lớn hơn hoặc bằng target đều được tính. Với target = 15, cửa sổ gồm 9, 3, 7 có tổng là 19 và vẫn có độ dài 3.

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

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

target = 15
nums = [4, 2, 9, 3, 7, 1, 5]

Đầu ra mong đợi

Minimum Size Subarray Sum

Hàm

Ràng buộc

Ví dụ

Gợi ý

Lời giải

Mở rộng từ mọi điểm bắt đầu

Tổng tiền tố và tìm kiếm nhị phân

Cửa sổ trượt

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

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

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