アルゴ AIに質問関連 1 問題

Two Pointers

二ポインタ

概要

配列やリストの両端（または同方向）に 2 本のポインタを置き、条件に応じて移動させながら目標を探す手法。ソート済み配列の 2 数和（Two Sum II）や回文判定など、 $O(n^2)$ の全探索を $O(n)$ に削減できる場面で活躍する。スライディングウィンドウは同方向の二ポインタの一形態。

計算量

操作	平均	最悪
走査（ソート済み配列）

ソート済みが前提の手法なので、問題文に sorted の記載がなければ $O(n \log n)$ のソートコストも含めて計算量を評価する必要がある。