Subarray Sum Equals K

+10

Bạn nhận được một mảng số nguyên nums và một số nguyên k. Hãy đếm số mảng con có tổng các phần tử bằng chính xác k. Mảng con là một dãy gồm một hoặc nhiều phần tử liền kề. Hai mảng con được tính riêng nếu chúng bắt đầu hoặc kết thúc ở các vị trí khác nhau, ngay cả khi chúng chứa các giá trị giống nhau. Các giá trị có thể là số âm hoặc số không.

Hàm

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

numsinteger-array: mảng số nguyên, có thể chứa các giá trị âm và số 0
kinteger: tổng mà một mảng con phải đạt được để được tính
Trả vềinteger: số mảng con có tổng các phần tử bằng k

Ràng buộc

1 ≤ nums.length ≤ 2 × 10⁴
-1000 ≤ nums[i] ≤ 1000
-10⁷ ≤ k ≤ 10⁷
Một mảng dài như vậy có nhiều nhất 200,010,000 mảng con, nên đáp án nằm trong phạm vi của số nguyên có dấu 32 bit.

Ví dụ

Đầu vào: nums = [3, 4, -7, 1, 3, 3, 1, -4]k = 7
Đầu ra: 4
Giải thích: Bốn lần chạy có tổng bằng 7: [3, 4], [1, 3, 3], [3, 3, 1] và [3, 4, -7, 1, 3, 3]. Trong lần cuối, -7 triệt tiêu 3 và 4.

Đầu vào: nums = [1, -1, 0]k = 0
Đầu ra: 3
Giải thích: Có ba mảng con có tổng bằng 0: [1, -1], [0] và toàn bộ mảng [1, -1, 0]. Đoạn [-1, 0] có tổng bằng -1 nên không được tính.

Đầu vào: nums = [2, 2, 2]k = 4
Đầu ra: 2
Giải thích: Dãy [2, 2] ở các chỉ số 0 và 1 và dãy [2, 2] ở các chỉ số 1 và 2 chứa cùng giá trị nhưng nằm ở các vị trí khác nhau, nên cả hai đều được tính.

Câu hỏi mở rộng

Làm thế nào để bạn sửa lời giải nhằm trả về độ dài của mảng con dài nhất có tổng bằng k, vẫn trong thời gian O(n)?

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 tối đa 2 × 10^8 mảng con quá chậm, còn các giá trị âm khiến ta không thể dùng cửa sổ trượt. Tổng của một mảng con là hiệu của hai tổng tiền tố, vì vậy với mỗi mảng con kết thúc tại đây, tổng của nó bằng k một lần cho mỗi tổng tiền tố trước đó bằng tổng tiền tố hiện tại trừ k. Bảng băm đếm các tổng đó chỉ trong một lượt duyệt.

Mỗi số bắt đầu bằng một tổng đang chạy

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

Ý tưởng

Cố định chỉ số đầu tiên start, sau đó dịch end sang phải và cộng nums[end] vào total đang tích lũy. Tổng này luôn chứa tổng các giá trị từ start đến end, vì vậy việc duyệt mọi cặp sẽ kiểm tra mỗi mảng con đúng một lần, mỗi lần chỉ cần một phép cộng.

Đừng dừng lại khi tổng vượt quá k. Một giá trị âm xuất hiện sau đó có thể kéo tổng xuống lại: trong ví dụ đầu tiên, tổng bắt đầu từ chỉ số 0 lần lượt là 3, 7, 0, 1, 4, 7, và có thêm một kết quả khớp tại chỉ số 5.

Độ phức tạp tính theo số cặp, khoảng 2 × 10^8 khi n = 2 × 10^4.

Thuật toán

Đặt count bằng 0.
Với mỗi start từ 0 đến n-1, đặt total bằng 0.
Với mỗi end từ start đến n-1, cộng nums[end] vào total.
Nếu total bằng k, cộng 1 vào count, rồi tiếp tục dù kết quả thế nào.
Trả về count.

def subarraySum(nums, k):
    n = len(nums)
    count = 0
    for start in range(n):
        total = 0
        # Grow the subarray that begins at start, one element at a time
        for end in range(start, n):
            total += nums[end]
            if total == k:
                count += 1
    return count

Tổng tiền tố với bản đồ đếm

Ý tưởng

Gọi prefix[j] là tổng của j phần tử đầu tiên, với prefix[0] = 0 cho tiền tố rỗng. Mảng con từ chỉ số i đến j-1 có tổng bằng prefix[j] - prefix[i]. Vì vậy, mỗi tổng tiền tố trước đó bằng tổng tiền tố hiện tại trừ k đánh dấu điểm bắt đầu của một mảng con khớp kết thúc tại đây. Hãy lưu số lần xuất hiện, không dùng tập hợp: mỗi lần một tổng tiền tố lặp lại, nó tạo thành một mảng con khác.

Trong ví dụ đầu tiên, các tổng tiền tố là 0, 3, 7, 0, 1, 4, 7, 8, 4. Số 7 đầu tiên tìm thấy một số 0, tạo thành [3, 4]. Số 7 thứ hai tìm thấy hai số 0, tạo thành [3, 4, -7, 1, 3, 3] và [1, 3, 3]. Số 8 tìm thấy một số 1, tạo thành [3, 3, 1].

Hãy tra cứu trước khi ghi lại tổng tiền tố hiện tại, nếu không, với k = 0, tổng tiền tố sẽ khớp với chính nó và tạo thành một mảng con rỗng. Mỗi phần tử cần một lần tra cứu và một lần cập nhật: độ phức tạp thời gian và không gian O(n).

Thuật toán

Tạo một từ điển seen với seen[0] = 1, và đặt prefix và count thành 0.
Với mỗi phần tử, cộng giá trị của nó vào prefix.
Cộng seen[prefix - k] vào count, đọc khóa không tồn tại là 0.
Cộng 1 vào seen[prefix].
Trả về count.

def subarraySum(nums, k):
    # seen[p] = how many prefixes so far add up to p; the empty prefix adds up to 0
    seen = {0: 1}
    prefix = 0
    count = 0
    for num in nums:
        prefix += num
        # Each earlier prefix equal to prefix - k starts a subarray that ends here and sums to k
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

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

Cửa sổ trượt thu nhỏ khi tổng vượt quá k sẽ không hoạt động với các giá trị âm: ở ví dụ đầu tiên, nó trả về 2 thay vì 4. Thoát khỏi vòng lặp bên trong của cách vét cạn tại thời điểm đó cũng gặp lỗi tương tự.
Bỏ qua seen[0] = 1. Với nums = [5] và k = 5, cách này trả về 0 thay vì 1.
Ghi lại tổng tiền tố hiện tại trước khi tra cứu. Với k = 0, [1, -1, 0] trả về 6 thay vì 3.
Dùng tập hợp các tổng tiền tố thay cho bản đồ đếm. Với [0, 0, 0] và k = 0, cách này bỏ sót các giá trị lặp lại; đáp án là 6.

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

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

Lời giải dùng tổng tiền tố và bản đồ băm chạy trong thời gian O(n) và dùng thêm O(n) bộ nhớ: duyệt một lượt, tra cứu một lần và cập nhật một lần cho mỗi phần tử. Kiểm tra mọi mảng con bằng tổng tích lũy mất thời gian O(n²).

Tại sao cửa sổ trượt không hiệu quả với bài toán tổng mảng con bằng K?

Cửa sổ trượt cần tổng tăng khi cửa sổ mở rộng và giảm khi cửa sổ thu hẹp. Giá trị âm phá vỡ tính chất đó: một cửa sổ quá lớn vẫn có thể trở thành cửa sổ khớp sau này, nên không có quy tắc nào xác định khi nào cần dịch cạnh trái. Khi chỉ có các giá trị dương, cửa sổ trượt giải quyết bài toán này trong thời gian O(n) và dùng O(1) bộ nhớ.

Tại sao bảng băm (hash map) bắt đầu bằng việc ánh xạ 0 thành 1?

Mục đó đại diện cho tiền tố rỗng trước phần tử đầu tiên, có tổng bằng 0. Một mảng con bắt đầu tại chỉ số 0 có tổng bằng tổng tiền tố hiện tại trừ đi 0, nên nếu không có mục đó, những mảng con này sẽ không bao giờ được đếm. Với nums = [5] và k = 5, phép tra cứu 5 - 5 = 0 sẽ tìm thấy mục đó.

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

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [3, 4, -7, 1, 3, 3, 1, -4]
k = 7

Đầu ra mong đợi