🔍 配列ペア数算出アルゴリズムの詳細解析
📋 問題定義
目標: 配列内で 1 ≤ j < i ≤ N かつ
Aj = Ai を満たすペア(i, j)の数を求める
制約: N ≤ 100,000、Ai ≤ 10^9、実行時間 ≤ 2秒、メモリ ≤ 1024MB
🎯 アルゴリズム概要
入力読み込み & 解析
↓
各値の出現回数をカウント
↓
組み合わせ数を計算
↓
結果出力
📊 ステップ1: 入力データの処理
入力例:
6
30
10
30
20
10
30
配列表現
🗂️ ステップ2: 出現回数のカウント
処理: Map<値, 出現回数>を構築
for (const num of arr) {
const currentCount = countMap.get(num) ?? 0;
countMap.set(num, currentCount + 1);
}
処理後のMap状態
値: 30
出現: 3回
値: 10
出現: 2回
値: 20
出現: 1回
🔢 ステップ3: 組み合わせ数の計算
公式: k個の同じ値から2個を選ぶ組み合わせ =
C(k,2) = k × (k-1) / 2
値 30 (3回出現)
C(3,2) = 3 × 2 / 2 = 3
具体的なペア:
• (2,0): A₂=A₀=30
• (5,0): A₅=A₀=30
• (5,2): A₅=A₂=30
値 10 (2回出現)
C(2,2) = 2 × 1 / 2 = 1
具体的なペア:
• (4,1): A₄=A₁=10
値 20 (1回出現)
C(1,2) = 0
具体的なペア:
なし（1個だけなのでペアを作れない）
総ペア数 = 3 + 1 + 0 = 4
⚡ 計算量解析
| 処理フェーズ |
時間計算量 |
空間計算量 |
詳細 |
| 入力読み込み |
O(N) |
O(N) |
配列全体を一度読み込み |
| 出現回数カウント |
O(N) |
O(K) |
Kは異なる値の数（最悪でO(N)） |
| 組み合わせ計算 |
O(K) |
O(1) |
Map内の各エントリを1回処理 |
| 総合計算量 |
O(N) |
O(N) |
線形時間で効率的 |
🚀 最適化のポイント
1. メモリ効率
-
Map使用: 配列全体のコピーではなく、値の出現回数のみ記録
-
型安全性:
TypeScriptの型システムで予期しないメモリ使用を防止
-
ガベージコレクション:
適切なスコープ管理でメモリリークを防止
2. 処理時間
- O(N)時間: 配列を一度だけスキャン、二重ループを回避
- Map操作: 平均O(1)でアクセス・更新
-
数学公式: 組み合わせ数を直接計算、ネストしたループを回避
3. 精度と安全性
- 整数演算: Math.floor()で明示的な整数変換
-
オーバーフロー対策: JavaScriptのNumber型の安全範囲内で計算
- エラーハンドリング: 入力制約の検証とtry-catch
🎯 実装の核心コード
function
countPairs(arr:
number[]):
number {
// Step 1: 出現回数をカウント
const countMap =
new
Map<number, number>();
for (const
num of arr) {
const currentCount =
countMap.get(num) ?? 0;
countMap.set(num, currentCount +
1);
}
// Step 2: 組み合わせ数を計算
let totalPairs:
number =
0;
for (const
count of countMap.values()) {
if (count >=
2) {
totalPairs +=
Math.floor((count * (count -
1)) /
2);
}
}
return totalPairs;
}
✅ 制約チェック
| 制約項目 |
制限値 |
実装での対応 |
安全マージン |
| 配列サイズ N |
≤ 100,000 |
O(N)の線形処理 |
✅ 十分に高速 |
| 実行時間 |
≤ 2秒 |
〜0.01秒 (推定) |
✅ 200倍のマージン |
| メモリ使用量 |
≤ 1024MB |
〜8MB (推定) |
✅ 128倍のマージン |
| 値の範囲 Ai |
≤ 10^9 |
Number型で安全に処理 |
✅ 完全対応 |