Arithmetic Slices ใน C++: นับ Subarray ที่เป็นเลขคณิต

โจทย์

Arithmetic Sequence = ลำดับ ≥ 3 ตัว ที่ความต่างระหว่างติดกันคงที่ หาจำนวน subarray (ต่อเนื่อง) ที่เป็น arithmetic slice

ตัวอย่าง: [1,2,3,4] → 3 slices: [1,2,3], [2,3,4], [1,2,3,4]

แนวคิด: DP นับ slice ที่ลงท้ายที่ i

ถ้า A[i] - A[i-1] == A[i-1] - A[i-2] แล้ว slice ที่ลงท้าย i-1 มี dp[i-1] ตัว → slice ที่ลงท้าย i เพิ่มขึ้น dp[i-1] + 1 ตัว (ต่อท้ายทุกตัว + ตัวใหม่ยาว 3)

ขั้นตอน

1. ret = 0, dp[n] = {0}
2. ลูป i = 2 ถึง n-1:
   • ถ้า A[i] - A[i-1] == A[i-1] - A[i-2]:
     • dp[i] = 1 + dp[i-1]
     • ret += dp[i]
3. คืน ret

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int ret = 0, n = A.size();
        vector<int> dp(n, 0);
        for (int i = 2; i < n; i++) {
            if (A[i] - A[i-1] == A[i-1] - A[i-2]) {
                dp[i] = 1 + dp[i-1];
                ret += dp[i];
            }
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,3,4};
    cout << ob.numberOfArithmeticSlices(v); // 3
    return 0;
}

อินพุต / เอาต์พุต

Input: [1,2,3,4]

Output: 3

ความซับซ้อน

• Time: O(n)
• Space: O(n) → สามารถลดเป็น O(1) ได้ (เก็บแค่ dp ก่อนหน้า)