Dãy số cộng dồn II - Dãy con trong C++

Cho mảng A gồm N số. Một dãy con (subsequence) là dãy chỉ số (K0, K1, ..., Kn) với 0 ≤ K0 < K1 < ... < Kn < N. Dãy con gọi là dãy cộng dồn nếu các giá trị A[K0], A[K1], ..., A[Kn] tạo thành cấp số cộng (chênh lệch giữa các phần tử liên tiếp bằng nhau) và n ≥ 2 (ít nhất 3 phần tử).

Ví dụ

A = [2, 4, 6, 8, 10] → có 7 dãy cộng dồn:

• Độ dài 3: [2,4,6], [2,4,10], [4,6,8], [6,8,10]
• Độ dài 4: [2,4,6,8], [4,6,8,10]
• Độ dài 5: [2,4,6,8,10]

Thuật toán: DP với Hash Map

dp[i][diff] = số dãy cộng dồn kết thúc tại chỉ số i với công sai diff (có độ dài ≥ 2).

1. Duyệt cặp (j, i) với j < i.
2. diff = A[i] - A[j].
3. Số dãy kết thúc ở j với công sai diff là temp = dp[j][diff] (mặc định 0).
4. Cộng temp vào kết quả (vì mỗi dãy đó mở rộng thêm A[i] thành dãy độ dài ≥ 3).
5. Nếu A[i] + diff tồn tại trong mảng (có thể mở rộng tiếp), cập nhật dp[i][diff] += temp + 1 (+1 cho cặp (j, i) mới).

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int ret = 0;
        unordered_map<lli, unordered_map<lli, lli>> dp;
        unordered_set<int> s(A.begin(), A.end());
        int n = A.size();
        for (int i = 1; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                lli diff = (lli)A[i] - (lli)A[j];
                if (diff <= INT_MIN || diff > INT_MAX) continue;
                int temp = dp[j].count(diff) ? dp[j][diff] : 0;
                ret += temp;
                if (s.count(A[i] + diff)) dp[i][diff] += temp + 1;
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {2, 4, 6, 8, 10};
    cout << ob.numberOfArithmeticSlices(v);
    return 0;
}

Độ phức tạp

• Thời gian: O(n^2) — duyệt tất cả cặp (j, i).
• Không gian: O(n^2) — lưu dp cho mỗi cặp (i, diff).

Input / Output

Input:  {2,4,6,8,10}
Output: 7