Array - tanakakenji/Rinko GitHub Wiki

1. はじめに

配列は同じ型の値を連続したメモリ位置に保持します。配列では通常、要素の位置/インデックスと要素自体の2つが重要です。プログラミング言語によって配列の実装が異なり、操作の時間複雑度に影響を与える場合があります。

Python、JavaScript、Ruby、PHPなどの言語では、配列（Pythonではリスト）のサイズが動的で、作成時にサイズを定義する必要がありません。そのため、これらの言語は面接で使いやすいとされています。

配列は面接で最も一般的なデータ構造の1つです。他のトピックに関する質問でも、配列/シーケンスが関係することが多いでしょう。配列の習得は面接に不可欠です！

2. 配列の利点と欠点

利点

• 単一の変数名で同じ型の複数の要素を格納できる
• インデックスさえあれば要素へのアクセスが速い（連結リストのように先頭から辿る必要がない）

欠点

• 配列の中央への要素の追加や削除は遅い（残りの要素をシフトする必要があるため）
• 固定サイズの配列では、初期化後にサイズを変更できない
• 挿入によって要素数が配列サイズを超える場合、新しい配列を割り当てて既存の要素をコピーする必要がある（O(n)の時間がかかる）

3. 学習リソース

読み物

• データ構造における配列: 定義と操作（Guru99）

動画

• 配列（カリフォルニア大学サンディエゴ校）

4. 一般的な用語

• 部分配列（Subarray）: 配列内の連続した値の範囲

  • 例: [2, 3, 6, 1, 5, 4] という配列がある場合、[3, 6, 1] は部分配列ですが、[3, 1, 5] は部分配列ではありません。

• 部分列（Subsequence）: 与えられた配列から、要素の順序を変えずに一部の要素を削除して得られる列

  • 例: [2, 3, 6, 1, 5, 4] という配列がある場合、[3, 1, 5] は部分列ですが、[3, 5, 1] は部分列ではありません。

5. 時間複雑度

操作	ビッグO表記	備考
アクセス	O(1)
検索	O(n)
検索（ソート済み配列）	O(log(n))
挿入	O(n)	後続の要素を右にシフトする必要があるため
挿入（末尾）	O(1)	他の要素をシフトする必要がない特殊なケース
削除	O(n)	後続の要素を左にシフトする必要があるため
削除（末尾）	O(1)	他の要素をシフトする必要がない特殊なケース

6. 面接時に注意すべきこと

• 配列に重複値があるかどうかを明確にする。重複値の存在が回答に影響するか？問題を簡単にするか難しくするか？
• インデックスを使って配列要素を反復処理する際は、境界を超えないよう注意する。
• コード内での配列のスライスや連結に注意する。通常、これらの操作にはO(n)の時間がかかる。可能な限り、開始インデックスと終了インデックスを使用して部分配列/範囲を示す。

7. コーナーケース

• 空の配列
• 1つまたは2つの要素を持つ配列
• 繰り返し要素を持つ配列
• 重複値を持つ配列

8. テクニック

注意: 配列と文字列はどちらもシーケンス（文字列は文字の配列）であるため、ここで紹介するテクニックの多くは文字列の問題にも適用できます。

1. スライディングウィンドウ

多くの部分配列/部分文字列の問題に適用できるスライディングウィンドウテクニックを習得しましょう。スライディングウィンドウでは、2つのポインタが通常同じ方向に移動し、互いに追い越すことはありません。これにより、各値が最大でも2回しか訪れられないことが保証され、時間複雑度はO(n)に抑えられます。

例題:

• 繰り返しのない最長部分文字列
• 最小サイズの部分配列の和
• 最小ウィンドウ部分文字列

2. 2つのポインタ

2つのポインタは、スライディングウィンドウのより一般的なバージョンで、ポインタが交差したり、異なる配列上にあったりする場合があります。

例題:

• 色の並べ替え
• 回文部分文字列

2つの配列を処理する場合、各配列に1つずつインデックス（ポインタ）を使用して両方を走査/比較し、必要に応じて一方のポインタをインクリメントするのが一般的です。例えば、この方法を使用して2つのソート済み配列をマージします。

例題:

• ソート済み配列のマージ

3. 右からの走査

従来の左からではなく、右から配列を走査することが有効な場合があります。

例題:

• 日々の気温
• 列の中で見える人数

4. 配列のソート

• 配列がソートされているか、部分的にソートされているか？その場合、何らかの形の二分探索が可能かもしれません。これは通常、面接官がO(n)より速い解決策を求めていることを意味します。
• 配列をソートできるか？場合によっては、最初に配列をソートすることで問題が大幅に簡単になることがあります。ただし、配列要素の順序を保持する必要がある場合は、この方法は使えません。

例題:

• 区間のマージ
• 重複しない区間

5. 事前計算

部分配列の和や積が関係する問題では、ハッシュや接頭辞/接尾辞の和/積を使用した事前計算が役立つ場合があります。

例題:

• 自身を除く配列の積
• 最小サイズの部分配列の和
• LeetCodeの"prefix-sum"タグが付いた問題

6. インデックスをハッシュキーとして使用

シーケンスが与えられ、面接官がO(1)の空間を要求する場合、配列自体をハッシュテーブルとして使用できる可能性があります。例えば、配列に1からN（Nは配列の長さ）までの値しかない場合、そのインデックス（マイナス1）の値を否定することで、その数値の存在を示すことができます。

例題:

• 最初の欠落する正の整数
• 日々の気温

7. 配列を複数回走査する

明白かもしれませんが、配列を2回または3回（n回未満である限り）走査してもO(n)です。配列を複数回走査することで、時間複雑度をO(n)に保ちながら問題を解決できる場合があります。

例題:

• 問題: 平衡インデックスを見つける

これらのテクニックを習得し、適切に応用することで、配列に関する多くの問題を効率的に解決できるようになります。実際の問題を解きながら、これらのテクニックを練習することをお勧めします。