Longest Subarray with Sum K

+10

Cho các số nguyên nums và giá trị mục tiêu k, hãy trả về độ dài của mảng con dài nhất có tổng các phần tử đúng bằng k. Mảng con là một đoạn gồm các phần tử liên tiếp, có độ dài ít nhất một. Một số giá trị có thể bằng không hoặc nhỏ hơn không. Nếu không có mảng con nào có tổng bằng k, hãy trả về 0.

Hàm

longestSubarrayWithSumK(nums: integer-array, k: integer) → integer

numsinteger-array: các số nguyên cần tìm, bao gồm cả số âm và số không
kinteger: tổng chính xác mà mảng con phải có
Trả vềinteger: độ dài của mảng con dài nhất có tổng bằng k, hoặc 0 nếu không có mảng nào như vậy

Ràng buộc

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
-10⁹ ≤ k ≤ 10⁹
Mọi tổng tiền tố đều nằm trong khoảng từ -2 × 10⁸ đến 2 × 10⁸, vì vậy số nguyên 32 bit là đủ.
Trả về 0 khi không có mảng con nào có tổng bằng k.

Ví dụ

Đầu vào: nums = [2, -1, 3, 1, -4, 2, 3]k = 5
Đầu ra: 5
Giải thích: Ba đoạn liên tiếp có tổng bằng 5: [2, 3] ở cuối, [2, -1, 3, 1] ở đầu và [3, 1, -4, 2, 3] từ chỉ số 2 đến 6. Đoạn cuối dài nhất, gồm 5 phần tử.

Đầu vào: nums = [4, 1, 1, 2, -1, 1]k = 3
Đầu ra: 4
Giải thích: [1, 1, 2, -1] ở các chỉ số từ 1 đến 4 và [1, 2, -1, 1] ở các chỉ số từ 2 đến 5 đều có tổng bằng 3 với 4 phần tử. Bạn trả về một độ dài, nên trường hợp hòa không quan trọng.

Câu hỏi mở rộng

Làm thế nào để tìm mảng con dài nhất có tổng không vượt quá k, trong đó vẫn cho phép các giá trị âm?

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

Tổng lũy kế giúp tính tổng của mọi mảng con chỉ bằng một phép trừ: các phần tử sau chỉ số s đến chỉ số i có tổng là prefix[i] - prefix[s]. Hãy ghi nhớ chỉ số đầu tiên nơi mỗi tổng xuất hiện, rồi duyệt qua một lượt để tìm đoạn khớp dài nhất kết thúc tại từng vị trí.

Mở rộng từng mảng con từ mỗi vị trí bắt đầu

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

Ý tưởng

Bắt đầu từ mỗi vị trí, mở rộng sang phải và cộng từng phần tử vào tổng đang tính. Mỗi khi tổng bằng k, hãy ghi lại độ dài. Mỗi mảng con tương ứng với một cặp vị trí bắt đầu và kết thúc, nên không bỏ sót mảng nào. Tiếp tục mở rộng ngay cả khi tổng vượt quá k: từ chỉ số 2 trong ví dụ đầu tiên, các tổng lần lượt là 3, 4, 0, 2, 5, và số -4 là lý do tổng cuối cùng đạt 5.

Có khoảng n²/2 cặp: 2 × 10^8 phép cộng khi n = 2 × 10^4.

Thuật toán

Đặt best thành 0.
Với mỗi start, đặt total thành 0.
Di chuyển end từ start đến chỉ số cuối cùng và cộng nums[end] vào total.
Khi total bằng k, đặt best thành giá trị lớn hơn giữa best và end - start + 1.
Trả về best.

def longestSubarrayWithSumK(nums, k):
    n = len(nums)
    best = 0
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            # A match may come after the total has passed k, so never stop early
            if total == k and end - start + 1 > best:
                best = end - start + 1
    return best

Tổng tiền tố với chỉ số đầu tiên của mỗi tổng

Ý tưởng

Một đoạn kết thúc tại chỉ số i có tổng bằng k khi và chỉ khi một tổng trước đó bằng prefix - k. Nếu có nhiều tổng trước đó thỏa mãn, tổng xuất hiện đầu tiên sẽ bắt đầu đoạn dài nhất, vì vậy bản đồ chỉ lưu mỗi tổng vào lần đầu tiên nó xuất hiện. Một bản sao xuất hiện sau đó chỉ có thể bắt đầu một đoạn ngắn hơn. Khởi tạo bản đồ với tổng 0 tại chỉ số -1, để một kết quả khớp bắt đầu tại chỉ số 0 có độ dài i + 1.

Trong ví dụ đầu tiên, các tổng lần lượt là 2, 1, 4, 5, 1, 3, 6. Tại chỉ số 6, 6 - 5 = 1 xuất hiện lần đầu tại chỉ số 1, tạo thành đoạn có độ dài 5. Tổng 1 xuất hiện lại tại chỉ số 4, và việc giữ lại chỉ số 1 giúp tìm được đoạn đó.

Mỗi phần tử chỉ cần tra cứu một lần, nên thời gian chạy là O(n), và bản đồ chứa tối đa n + 1 tổng.

Thuật toán

Tạo một từ điển first lưu tổng 0 tại chỉ số -1, rồi đặt prefix và best thành 0.
Với mỗi chỉ số i, cộng nums[i] vào prefix.
Nếu prefix - k có trong từ điển tại chỉ số start, đặt best thành giá trị lớn hơn giữa best và i - start.
Nếu prefix chưa có trong từ điển, lưu nó cùng với chỉ số i.
Trả về best.

def longestSubarrayWithSumK(nums, k):
    # first[p] is the index where the prefix sum p first appears; the empty prefix sits at -1
    first = {0: -1}
    prefix = 0
    best = 0
    for i, num in enumerate(nums):
        prefix += num
        # The earliest prefix equal to prefix - k starts the longest match that ends at i
        start = first.get(prefix - k)
        if start is not None and i - start > best:
            best = i - start
        # Keep the first index only: a later one could only start a shorter subarray
        if prefix not in first:
            first[prefix] = i
    return best

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

Ghi đè chỉ số đã lưu mỗi khi tổng lặp lại sẽ giữ vị trí bắt đầu mới nhất và tìm được đoạn khớp ngắn hơn. Ở ví dụ đầu tiên, cách này trả về 4 thay vì 5, vì tổng 1 chuyển từ chỉ số 1 sang chỉ số 4.
Cửa sổ co lại khi tổng của nó lớn hơn k cũng trả về 4 ở ví dụ đầu tiên. Cuối cùng, cửa sổ chứa [-1, 3, 1, -4, 2, 3] với tổng bằng 4 và không bao giờ loại bỏ -1.
Bỏ qua tổng 0 tại chỉ số -1 sẽ bỏ sót mọi kết quả khớp bắt đầu ở chỉ số 0: [5, 0, 0, 0] với k = 5 trả về 0 thay vì 4.
Chỉ số đã lưu là vị trí trước mảng con, vì vậy độ dài là i - start. Cộng thêm 1 sẽ đếm thừa một phần tử.

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

Độ phức tạp thời gian của bài toán mảng con dài nhất có tổng bằng K là gì?

Độ phức tạp thời gian O(n) và không gian phụ O(n) nhờ tổng tích lũy và một bản đồ lưu chỉ số đầu tiên: mỗi phần tử cần một lần tra cứu và nhiều nhất một lần chèn. Mở rộng từng mảng con từ mỗi vị trí bắt đầu tốn thời gian O(n²) và không gian O(1).

Tại sao cửa sổ trượt không hoạt động khi mảng có số âm?

Kỹ thuật cửa sổ trượt giả định rằng thêm một phần tử sẽ làm tăng tổng, còn bỏ đi một phần tử sẽ làm giảm tổng. Với các giá trị âm, cửa sổ có tổng quá lớn vẫn có thể đạt k khi thêm một phần tử âm, còn cửa sổ có tổng quá nhỏ có thể cần bỏ đi một phần tử âm ở bên trái. Cửa sổ không thể xác định bước nào là đúng.

Có thể tìm mảng con dài nhất có tổng bằng K với độ phức tạp bộ nhớ phụ O(1) không?

Chỉ khi không có giá trị nào âm. Khi đó, tổng không bao giờ giảm khi cửa sổ mở rộng, và hai con trỏ tìm cửa sổ dài nhất có tổng k trong thời gian O(n) và không gian O(1). Nếu có giá trị âm, bạn cần dùng bản đồ các tổng hoặc cách duyệt O(n²).

def longestSubarrayWithSumK(nums, k):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [2, -1, 3, 1, -4, 2, 3]
k = 5

Đầu ra mong đợi