Đếm mảng con có các phần tử liên tiếp chênh lệch 1 trong C++

Cho mảng arr[]. Đếm mảng con mà các phần tử liên tiếp trong mảng con chênh lệch nhau đúng 1. Ví dụ [1,2,3] → [1,2], [2,3], [1,2,3].

Ví dụ

Đầu vào: arr[] = {4,3,2,1}
Đầu ra: 6
Giải thích: [4,3], [3,2], [2,1], [4,3,2], [3,2,1], [4,3,2,1].

Đầu vào: arr[] = {1,5,6,7,9,11}
Đầu ra: 3
Giải thích: [5,6], [6,7], [5,6,7].

Giải thuật

Duyệt mảng, tìm các đoạn liên tiếp mà phần tử chênh lệch 1. Với đoạn dài temp, số mảng con có độ dài ≥ 2 là temp * (temp - 1) / 2.

Ví dụ triển khai

#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;
}

Kết quả

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