問題: 平衡インデックスを見つける - tanakakenji/Rinko GitHub Wiki

問題文

整数の配列が与えられます。配列の「平衡インデックス」を見つけてください。平衡インデックスとは、そのインデックスの左側の要素の合計が、右側の要素の合計と等しくなるインデックスのことです。

配列の左端より左側の要素の合計は0とし、右端より右側の要素の合計も0とします。

平衡インデックスが存在する場合はそのインデックスを、存在しない場合は-1を返してください。

例: 入力: [1,2,3,4,3,2,1] 出力: 3 説明: インデックス3（値は4）の左側の合計は1+2+3=6、右側の合計も3+2+1=6です。

解答 (C++)

#include <vector>
#include <numeric>
#include <iostream>

class Solution {
public:
    int findEquilibriumIndex(std::vector<int>& nums) {
        int n = nums.size();
        
        // 第1回走査: 全要素の合計を計算
        int totalSum = std::accumulate(nums.begin(), nums.end(), 0);
        
        // 第2回走査: 平衡インデックスを探す
        int leftSum = 0;
        for (int i = 0; i < n; i++) {
            // 右側の合計 = 全体の合計 - 左側の合計 - 現在の要素
            if (leftSum == totalSum - leftSum - nums[i]) {
                return i;
            }
            leftSum += nums[i];
        }
        
        // 平衡インデックスが見つからない場合
        return -1;
    }
};

// テスト用のメイン関数
int main() {
    Solution sol;
    std::vector<int> nums = {1, 2, 3, 4, 3, 2, 1};
    int result = sol.findEquilibriumIndex(nums);
    
    std::cout << "The equilibrium index is: " << result << std::endl;
    
    return 0;
}

cppCopyint totalSum = std::accumulate(nums.begin(), nums.end(), 0); この行は、C++の標準ライブラリ関数 std::accumulate を使用して、nums ベクター内の全ての要素の合計を計算しています。

std::accumulate 関数:

これは ヘッダーに定義されている関数です。 指定された範囲内の要素を累積的に合計（または他の操作を適用）します。

引数の説明:

第1引数 nums.begin(): 累積を開始する位置（イテレータ） 第2引数 nums.end(): 累積を終了する位置（イテレータ） 第3引数 0: 初期値。ここでは0から累積を開始します。

動作:

nums の先頭から末尾まで順に各要素を走査します。 各要素を初期値（この場合は0）に加算していきます。 最終的に、全要素の合計が返されます。

型の推論:

返り値の型は、第3引数の型（この場合は int）と nums の要素の型に基づいて決定されます。

パフォーマンス:

この関数は内部で最適化されており、単純なループよりも効率的に動作する可能性があります。

使用例: 例えば、nums が {1, 2, 3, 4, 3, 2, 1} の場合、 totalSum は 1 + 2 + 3 + 4 + 3 + 2 + 1 = 16 となります。

この関数を使用することで、配列の合計を簡潔かつ効率的に計算できます。また、標準ライブラリ関数を使用することで、コードの可読性と保守性が向上します。

解説

  1. 複数回走査の活用:

    • このアルゴリズムでは、配列を2回走査しています。
    • 1回目の走査で全要素の合計を計算し、2回目の走査で平衡インデックスを探しています。

  2. 時間複雑度:

    • 2回の走査を行っていますが、各走査はO(n)の時間がかかるため、全体の時間複雑度はO(n)です。

  3. 空間複雑度:

    • 追加の配列やデータ構造を使用していないため、空間複雑度はO(1)です。

  4. アルゴリズムの流れ:

    • 第1回走査: std::accumulateを使用して全要素の合計を計算します。
    • 第2回走査: 左側の合計を徐々に増やしながら、各インデックスで左右の合計を比較します。

  5. 効率性:

    • 2回の走査を行うことで、1回の走査で解決しようとする場合に比べて、アルゴリズムがシンプルになっています。
    • 全体の合計を事前に計算することで、各インデックスでの右側の合計を効率的に求められます。

  6. C++固有の特徴:

    • std::accumulateを使用して、配列の合計を効率的に計算しています。
    • 範囲ベースのfor文を使用せず、インデックスを明示的に扱うことで、左側の合計を簡単に追跡できています。

  7. 面接でのポイント:

    • なぜ2回の走査が必要か、また2回の走査で十分であることを説明できることが重要です。
    • 時間複雑度がO(n)であることを説明できるようにしましょう。
    • 空間複雑度を最小限に抑えている点も強調できます。

この問題は、配列を複数回走査することで、アルゴリズムを単純化し、効率的に解決できる良い例です。1回の走査でも解決可能ですが、2回の走査を用いることで、コードがより読みやすく、理解しやすくなっています。これは、特に複雑な問題を単純化したい場合や、コードの可読性を重視する場合に有用なテクニックです。

⚠️ **GitHub.com Fallback** ⚠️