Đếm số lượng mảng con có tổng bằng x

Bài toán: Cho một mảng gồm n số nguyên dương (1≤n≤2⋅10^5), nhiệm vụ của bạn là đếm số mảng con (dãy con các phần tử liên tiếp) có tổng bằng x.

Các thuật toán

Bài toán đếm số lượng mảng con có tổng bằng x trong một mảng gồm n số nguyên dương có thể được giải bằng các thuật toán sau:

  1. Thuật toán liệt kê tất cả các mảng con có thể trong mảng ban đầu và đếm số lượng mảng con có tổng bằng x. Độ phức tạp của thuật toán này là O(n^3), với n là số lượng phần tử trong mảng ban đầu.

  2. Sử dụng kỹ thuật quét qua mảng (sliding window) để duyệt qua các mảng con liên tiếp của mảng ban đầu. Trong quá trình duyệt, tính tổng các phần tử của mảng con và so sánh với giá trị x. Nếu tổng bằng x, tăng biến đếm lên 1. Độ phức tạp của thuật toán này là O(n), với n là số lượng phần tử trong mảng ban đầu.

  3. Sử dụng kỹ thuật quy hoạch động (dynamic programming) để tìm số lượng mảng con có tổng bằng x. Xây dựng một ma trận dp[i][j] có giá trị là số lượng mảng con trong đoạn từ vị trí 1 đến i có tổng bằng j. Từ đó, ta có thể tính được số lượng mảng con trong toàn bộ mảng có tổng bằng x là dp[n][x]. Độ phức tạp của thuật toán này là O(nx), với n là số lượng phần tử trong mảng ban đầu và x là giá trị cần tìm.

Chúng ta tập trung vào hai thuật toán cuối vì độ phức tạp tối ưu hơn.

Thuật toán sliding window

Để giải bài toán đếm số lượng mảng con có tổng bằng x trong một mảng gồm n số nguyên dương bằng thuật toán sliding window, ta có thể thực hiện các bước sau:

  1. Khởi tạo biến đếm số lượng mảng con có tổng bằng x là cnt = 0.

  2. Khởi tạo biến left và right đại diện cho hai đầu mút của cửa sổ trượt ban đầu, ban đầu left = 0 và right = 0.

  3. Khởi tạo biến sum đại diện cho tổng của các phần tử trong mảng con đang xét, ban đầu sum = a[0] (a là mảng đầu vào).

  4. Duyệt qua mảng từ vị trí đầu tiên đến vị trí cuối cùng. Trong quá trình duyệt, thực hiện các bước sau:

  • Tính tổng sum của các phần tử trong mảng con từ left đến right.

  • Nếu tổng sum bằng x, tăng biến đếm cnt lên 1.

  • Nếu tổng sum nhỏ hơn x, di chuyển right sang phải và cập nhật giá trị sum bằng sum + a[right].

  • Nếu tổng sum lớn hơn x, di chuyển left sang phải và cập nhật giá trị sum bằng sum – a[left].

  1. Sau khi duyệt hết mảng, biến cnt sẽ lưu số lượng mảng con có tổng bằng x.

  2. Trả về giá trị cnt là kết quả của bài toán.

Thuật toán sliding window có độ phức tạp là O(n), với n là số lượng phần tử trong mảng ban đầu.

Dưới đây là một đoạn code Python đầy đủ để giải bài toán đếm số lượng dãy con có tổng bằng x sử dụng thuật toán sliding window:

def count_subarrays(arr, n, x):
    count = 0
    window_sum = 0
    start = 0

    for end in range(n):
        window_sum += arr[end]

        while window_sum > x and start < end:
            window_sum -= arr[start]
            start += 1

        if window_sum == x:
            count += 1

    return count

n, x = map(int, input().split())
arr = list(map(int, input().split()))

print(count_subarrays(arr, n, x))

Trong đó:

  • arr là mảng đầu vào.
  • n là kích thước của mảng.
  • x là tổng mục tiêu.
  • count là biến đếm số lượng dãy con có tổng bằng x.
  • window_sum là tổng của các phần tử trong cửa sổ trượt hiện tại.
  • start là chỉ số bắt đầu của cửa sổ trượt.
  • end là chỉ số kết thúc của cửa sổ trượt.

Thuật toán này sử dụng một cửa sổ trượt để duyệt qua từng dãy con của mảng và kiểm tra tổng của dãy con đó có bằng x không. Nếu tổng bằng x, tăng biến count lên một. Nếu tổng lớn hơn x, di chuyển cửa sổ trượt về phía trái để loại bỏ các phần tử không cần thiết.

Ở đoạn code này, đầu vào của chương trình được nhập từ bàn phím và kết quả được in ra màn hình.

Thuật toán quy hoạch động

Để giải bài toán đếm số lượng mảng con có tổng bằng x trong một mảng gồm n số nguyên dương bằng thuật toán quy hoạch động, ta có thể thực hiện các bước sau:

  1. Khởi tạo một mảng độ dài n+1, gọi là dp, để lưu trữ số lượng mảng con có tổng bằng một số nguyên k từ đầu đến vị trí i của mảng ban đầu. Ban đầu, tất cả các giá trị trong mảng dp đều bằng 0, trừ dp[0] = 1 để đảm bảo trường hợp tổng bằng 0 được tính vào kết quả.

  2. Khởi tạo biến sum để lưu tổng của các phần tử trong mảng con đang xét, ban đầu sum = 0.

  3. Duyệt qua từng phần tử trong mảng ban đầu từ đầu đến cuối. Trong quá trình duyệt, thực hiện các bước sau:

  • Cập nhật giá trị sum bằng sum + a[i], với a là mảng đầu vào.

  • Duyệt qua các giá trị j từ 0 đến i-1, cập nhật giá trị dp[i] bằng dp[i] + dp[j] nếu tổng của các phần tử trong đoạn từ j+1 đến i bằng x.

  1. Sau khi duyệt hết mảng, giá trị dp[n] sẽ lưu số lượng mảng con có tổng bằng x.

  2. Trả về giá trị dp[n] là kết quả của bài toán.

Thuật toán quy hoạch động có độ phức tạp là O(n^2), với n là số lượng phần tử trong mảng ban đầu. Tuy nhiên, có thể tối ưu thuật toán này để giảm độ phức tạp xuống còn O(n) bằng cách sử dụng một mảng đơn chiều và thực hiện cập nhật trực tiếp giá trị dp[i] từ dp[i-x] (với x là giá trị của phần tử hiện tại đang xét) mà không cần duyệt qua các giá trị j từ 0 đến i-1 như trên.

Dưới đây là một đoạn code Python đầy đủ để giải bài toán đếm số lượng dãy con có tổng bằng x sử dụng thuật toán quy hoạch động:

def count_subarrays(arr, n, x):
    # Khởi tạo bảng đếm số lượng dãy con có tổng bằng các giá trị từ 0 đến x
    dp = [0] * (x + 1)
    dp[0] = 1

    # Duyệt qua từng phần tử của mảng và cập nhật bảng đếm
    for i in range(n):
        for j in range(x, arr[i] - 1, -1):
            dp[j] += dp[j - arr[i]]

    return dp[x]

n, x = map(int, input().split())
arr = list(map(int, input().split()))

print(count_subarrays(arr, n, x))

Trong đó:

  • arr là mảng đầu vào.
  • n là kích thước của mảng.
  • x là tổng mục tiêu.
  • dp là bảng đếm số lượng dãy con có tổng bằng các giá trị từ 0 đến x.
  • Biến ij được sử dụng để duyệt qua từng phần tử của mảng và cập nhật bảng đếm.

Thuật toán này sử dụng một bảng đếm để lưu số lượng dãy con có tổng bằng các giá trị từ 0 đến x. Ban đầu, bảng đếm được khởi tạo sao cho chỉ có một dãy con rỗng có tổng bằng 0.

Sau đó, chương trình duyệt qua từng phần tử của mảng và cập nhật bảng đếm bằng cách tính toán số lượng dãy con có tổng bằng j dựa trên số lượng dãy con có tổng bằng j - arr[i]. Kết quả cuối cùng là giá trị tại ô (x) của bảng đếm.

Ở đoạn code này, đầu vào của chương trình được nhập từ bàn phím và kết quả được in ra màn hình./.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *