นับ Subarray ที่สมาชิกติดกันต่างกัน 1 ใน C++

เราได้รับอาร์เรย์ arr[] เป้าหมายคือนับ subarray ที่สมาชิกติดกันทุกคู่อย่างต่างกัน 1 (เช่น 1,2,3 หรือ 4,3,2)

ตัวอย่าง

อินพุต: arr[] = {4, 3, 2, 1}

เอาต์พุต: 6

คำอธิบาย: [4,3], [3,2], [2,1], [4,3,2], [3,2,1], [4,3,2,1]

อินพุต: arr[] = {1, 5, 6, 7, 9, 11}

เอาต์พุต: 3

คำอธิบาย: [5,6], [6,7], [5,6,7]

แนวทางการแก้ปัญหา

วนลูปอาร์เรย์ ตรวจสอบว่า |arr[i] - arr[i-1]| == 1 ถ้าใช่ต่อยอดกลุ่ม ถ้าไม่ ให้คำนวณ subarray ในกลุ่มที่จบด้วยสูตร n × (n-1) / 2 (n = ความยาวกลุ่ม)

การนำไปใช้ (Implementation)

#include <iostream>
using namespace std;

int sub_ele_diff_one(int arr[], int size) {
    int count = 0, first = 0, last = 0;
    for (int i = 1; i < size; i++) {
        if (abs(arr[i] - arr[i-1]) == 1) {
            first++;
        } else {
            int temp = first - last + 1;
            int total = temp * (temp - 1) / 2;
            count += total;
            first = i;
            last = i;
        }
    }
    if (first != last) {
        int temp = first - last + 1;
        int total = temp * (temp - 1) / 2;
        count += total;
    }
    return count;
}

int main() {
    int arr[] = {1, 2, 4, 3};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of Subarrays with Consecutive elements differing by 1 are: " << sub_ele_diff_one(arr, size);
    return 0;
}

เอาต์พุต

Count of Subarrays with Consecutive elements differing by 1 are: 2