【C++】連続する部分配列の合計がkの倍数になるかを判定するアルゴリズム

問題概要

負でない数値のリストと目標となる整数 k が与えられたとき、長さが2以上の連続する部分配列（サブアレイ）の中に、合計が k の倍数（つまり n × k、n は任意の整数）となるものが存在するかどうかを判定する関数を作成します。

例えば、入力が [23, 2, 4, 6, 7] で k = 6 の場合を考えてみましょう。[2, 4] は長さ2の連続部分配列であり、その合計は 6 で k の倍数に一致するため、結果は True（真） となります。

解法のアプローチ：累積和の剰余とハッシュマップ

この問題は、累積和（プレフィックスサム）の剰余とハッシュマップを組み合わせることで、O(n) の時間計算量で効率的に解くことができます。

解法の手順

• ハッシュマップ m を用意し、初期値として m[0] = -1 を設定します。また、sum = 0、n = nums のサイズ とします。
• i を 0 から n − 1 まで順に処理します。
  • sum += nums[i] として累積和を更新します。
  • k が 0 以外の場合、sum %= k で剰余を取ります。
  • m に sum が既に存在し、かつ i − m[sum] >= 2 を満たす場合は true を返します。
  • m に sum が存在しない場合は、m[sum] = i として現在のインデックスを登録します。
• ループ完了後も条件を満たす部分配列が見つからなければ、false を返します。

なぜこの方法が有効なのか

重要なポイントは、「2つの異なるインデックスで累積和の剰余が等しい場合、その間の部分配列の合計は必ず k の倍数になる」という性質です。また、m[0] = -1 を事前に登録しておくことで、配列の先頭から始まる部分配列も正しく判定できるようになります。さらに、「インデックスの差が2以上」という条件を設けることで、長さ1の部分配列が誤ってマッチするのを防いでいます。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> m;
        m[0] = -1;
        int sum = 0;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            sum += nums[i];
            if(k)
            sum %= k;
            if(m.count(sum) && i - m[sum] >= 2){
                return true;
            }
            if(!m.count(sum)) m[sum] = i;
        }
        return false;
    }
};
main(){
    vector<int> v = {23,2,4,6,7};
    Solution ob;
    cout << (ob.checkSubarraySum(v, 6));
}

入力

[23,2,4,6,7]
6

出力

1

出力が 1 となっているのは、関数が true を返したこと、つまり条件を満たす連続部分配列 [2, 4] が存在することを示しています。