C++で隣接する要素の差が1である部分配列を数える方法

問題の概要

整数を含む配列 arr[] が与えられたとき、各部分配列内で隣り合う要素同士の差がちょうど1になるような部分配列をすべて数えることが目標です。例えば、配列が [1,2,3] の場合、該当する部分配列は [1,2]、[2,3]、[1,2,3] のみとなります。

具体的な例で確認してみましょう。

入力例 1

arr[] = { 4, 3, 2, 1 }

出力 − 隣接要素の差が1である部分配列の個数 − 6

解説 − 該当する部分配列は以下の通りです。

[4,3], [3,2], [2,1], [4,3,2], [3,2,1], [4,3,2,1]
合計 6 個

入力例 2

arr[] = { 1, 5, 6, 7, 9, 11 }

出力 − 隣接要素の差が1である部分配列の個数 − 3

解説 − 該当する部分配列は以下の通りです。

[5,6], [6,7], [5,6,7]
合計 3 個

プログラムで採用するアプローチ

forループを用いて配列を先頭から順に走査し(i = 1 から i < size まで)、各要素が直前の要素と1だけ異なっているかどうかを判定していきます。条件を満たす間はインデックス first を進め、条件が崩れた時点で、それまでの区間(first〜last)に含まれる要素数を temp = first − last + 1 として求めます。この区間内ではすべての隣接要素が1だけ異なるため、取り得る部分配列の総数は temp × (temp − 1) / 2 となり、これを count に加算します。その後、first = last = i としてインデックスを更新し、次の連続区間の探索へ移ります。

• 整数の配列 arr[] を用意します。

• 関数 sub_ele_diff_one(int arr[], int size) が配列を受け取り、隣接要素の差が1である部分配列の個数を返します。

• カウント count の初期値を 0 とします。

• forループで i = 1 から i < size まで配列を走査します。

• 変数 first と last を 0 で初期化し、「すべての要素が連続していて差が1」となる区間のインデックス範囲を管理します。

• arr[i−1] − arr[i] == 1 または arr[i] − arr[i−1] == 1(隣接要素の差が1)であるかを判定し、真であれば first をインクリメントします。

• 条件が成り立たなかった場合、その区間の要素数は temp = first − last + 1、可能な部分配列数は total = temp × (temp − 1) / 2 となります。

• この total を count に加算します。

• first と last を現在の i(連続性が途切れた位置)で更新します。

• ループ終了後に first != last であれば、残りの区間も条件を満たしていることを意味します。同じ手順で total を求め、count に加算します。

• すべての処理が完了したら、count を結果として返します。

この手法により、配列全体を一度走査するだけで答えが求まるため、計算量は O(n) と非常に効率的です。

実装例

#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 (arr[i] - arr[i - 1] == 1 || arr[i-1] - arr[i] == 1){
            first++;
        }
        else{
            int temp = first - last + 1;
            int total = temp * (temp - 1) / 2;
            count = count + total;
            first = i;
            last = i;
        }
    }
    if (first != last){
        int temp = first - last + 1;
        int total = temp * (temp - 1) / 2;
        count = 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

この例では、配列 { 1, 2, 4, 3 } において条件を満たす部分配列は [1,2] と [4,3] の2つであるため、正しく 2 が出力されています。