Section 2・3 では「1回の操作を速くする」ことを学びました。
Section 4 は「同じデータに対してクエリが何度も来る」という状況を扱います。
1回のクエリを速くするだけでなく、「最初に一度だけ前処理を済ませておく」設計がポイントです。
前半（問題 20〜24）では累積和・文字位置インデックス・top-k を扱います。
前処理に O(n) かけておくことで、各クエリが O(1) になる設計です。
後半（問題 25〜28）ではスライディングウィンドウを扱います。
ウィンドウを固定幅で滑らせる問題（問題25）、可変幅ウィンドウ（問題26）、Kadane 法（問題27）、2Sum（問題28）と進みます。
問題28（2Sum）は Section 2 で学んだ「視点の反転＋ハッシュテーブル」の直接応用です。
Section 2 の技法が Section 4 の設計と融合する問題です。
1. 問題20 前処理による区間和クエリの高速化
整数ベクタ vec が与えられます。make-prefix-sums で前処理し、クエリ (i j) に対して vec[i] + vec[i+1] + ... + vec[j-1] を O(1) で答える range-sum-fast を実装してください。
vec = #(1 2 3 4 5)
(let ((ps (make-prefix-sums vec)))
(range-sum-fast ps 0 3)) → 6 (1+2+3)
(range-sum-fast ps 1 4)) → 9 (2+3+4)
(range-sum-fast ps 0 5)) → 15 (全体)
(range-sum-fast ps 2 3)) → 3 (3のみ)Code language: Lisp (lisp)AtCoder では「Q 個の区間クエリに答えよ」という形式が頻出です。
各クエリに O(n) かけると Q × n の計算量になりますが、累積和を前処理しておけば前処理 O(n)・各クエリ O(1) になります。
1.1. 素直な実装 — クエリ1件あたり O(j – i)
q 件のクエリがあれば合計 O(q × n)。
(defun range-sum-naive (vec i j)
"区間 [i, j) の和を毎回足し合わせる。"
(let ((sum 0))
(loop for k from i below j do
(incf sum (aref vec k)))
sum))Code language: Lisp (lisp)1.2. 効く実装 — 前処理 O(n)、クエリ O(1)
事前に累積和を作っておくと、毎回合計を計算し直さないでも答えを求めることができます。
累積和は、ps[k] = vec[0] + vec[1] + … + vec[k-1] です。
(defun make-prefix-sums (vec)
"累積和（prefix sum）配列を構築する。"
(let* ((n (length vec))
(ps (make-array (1+ n) :initial-element 0)))
(loop for k from 0 below n do
(setf (aref ps (1+ k))
(+ (aref ps k) (aref vec k))))
ps))
(defun range-sum-fast (ps i j)
"累積和から区間 [i, j) の和を O(1) で返す。"
(- (aref ps j) (aref ps i)))Code language: Lisp (lisp)たとえば、vec[1] + vec[2] + vec[3]は、累積和 ps を使うと ps[4] – ps[1] で計算できるからです。
vec = [1, 2, 3, 4, 5]
ps = [0, 1, 3, 6, 10, 15]
range-sum(ps, 1, 4) = ps[4] - ps[1] = 10 - 1 = 9
= vec[1] + vec[2] + vec[3] = 2 + 3 + 4 ✓ps[0] = 0 （空区間の和）のため、累積和の配列サイズは、1つ余分に作る必要があります。
あらかじめ make-prefix-sumsで累積和を用意したら、range-sum-fastに与えます。
(let* ((v #(1 2 3 4 5))
(ps (make-prefix-sums v)))
(range-sum-fast ps 1 4)) => 9 (2+3+4)Code language: Lisp (lisp)2次元への拡張（画像の矩形領域の合計など）：
(defun make-prefix-sums-2d (matrix rows cols)
"2次元累積和を構築する。"
(let ((ps (make-array (list (1+ rows) (1+ cols))
:initial-element 0)))
(loop for i from 1 to rows do
(loop for j from 1 to cols do
(setf (aref ps i j)
(+ (aref matrix (1- i) (1- j))
(aref ps (1- i) j)
(aref ps i (1- j))
(- (aref ps (1- i) (1- j))))))) ; 重複を引く
ps))Code language: Lisp (lisp)「同じ配列に対してクエリが多数来る」パターンは前処理で有利です。
1回 O(n) で O(1) クエリになれば、q 回のクエリで O(n + q) と O(nq) の差が生まれます。
2. 問題21 文字の出現位置の一覧を構築する
文字列 s を受け取り、各文字がどのインデックスに出現したかをハッシュテーブルで返す関数を書いてください。
入力: s = "abacaba"
出力: {# → (0 2 4 6), # → (1 5), #\c → (3)}
入力: s = "aaa"
出力: {# → (0 1 2)}
入力: s = "abcd"
出力: {# → (0), # → (1), #\c → (2), #\d → (3)}Code language: PHP (php)「文字 c の k 番目の出現位置はどこか」というクエリが大量に来る場面で、前処理として位置一覧を構築しておくと各クエリが O(1) になります。assoc と append を組み合わせると二重の線形コストが発生します。
問題20は値の集計でした。
問題21は位置の集計です。
各文字に対する問い合わせが後から来ることを想定した前処理になります。
2.1. 素直な実装 — O(n²)
(defun char-positions-naive (s)
"assoc で管理しながら append で位置を追記する。"
(let ((result nil))
(loop for i below (length s) do
(let* ((ch (char s i))
(cell (assoc ch result :test #'char=)))
(if cell
(setf (cdr cell) (append (cdr cell) (list i)))
(push (cons ch (list i)) result))))
result))Code language: Lisp (lisp)charは、O(1) で文字列の i 番目の文字を返しますが、assoc は走査に O(k) かかります。
append で末尾追記すると、O(現在のリスト長)になり、 二重の遅さになります。
2.2. 効く実装 — O(n) 期待値
連想リストの走査 assocの代わりに、ハッシュテーブルから取る gethashを使うと高速化できます。
(defun char-positions-fast (s)
"ハッシュテーブルで管理し push + nreverse パターンを使う。"
(let ((table (make-hash-table :test #'eql)))
(loop for i below (length s) do
(let ((ch (char s i)))
(setf (gethash ch table)
(cons i (gethash ch table nil)))))
(maphash (lambda (k v)
(setf (gethash k table) (nreverse v)))
table)
table))
;; 使用例
;; (char-positions-fast "abacaba")
;; => {#\a: (0 2 4 6), #\b: (1 5), #\c: (3)}Code language: Lisp (lisp)assoc と append の組み合わせは二重の線形コストを生みます。
ハッシュテーブルと push に変えて、まずは逆順にリストを作り、最後に maphash での整列すると O(n) で済みます。
Section 1 で学んだ「push と nreverse」のパターンがここでも登場します。
3. 問題22 出現頻度上位 k 個を求める
整数のリスト xs と整数 k を受け取り、出現回数の多い順に上位 k 個の (要素 . 回数) のペアをリストで返す関数を書いてください。
入力: xs = (1 2 2 3 3 3 4 4 4 4)
k = 2
出力: ((4 . 4) (3 . 3))
入力: xs = ("a" "b" "a" "c" "b" "a")
k = 2
出力: (("a" . 3) ("b" . 2))
入力: xs = (1 2 3)
k = 1
出力: ((1 . 1)) ← 同着の場合は順不同Code language: JavaScript (javascript)「アクセスログから最もアクセスの多い URL を求める」「選挙結果を集計して上位 k 候補を表示する」などで使います。
頻度計算をハッシュテーブルで行うのがボトルネック解消の核心です。
問題7（頻度カウント）を前処理として活用する問題です。
「まず集計、次にソート」という2段階の設計を確認します。
3.1. 素直な実装 — 頻度計算が O(n²)
(defun top-k-naive (xs k)
;; frequencies-naive（問題7の assoc 版）は O(n²)。
(let ((freq (frequencies-naive xs)))
(subseq (sort (copy-list freq) #'> :key #'cdr)
0 k)))Code language: Lisp (lisp)3.2. 効く実装 — 頻度計算 O(n)、ソート O(m log m)
(defun top-k-fast (xs k)
"ハッシュテーブルで頻度集計してからペアリストをソート。"
(let ((table (frequencies-fast xs)) ; 問題7のハッシュ版。O(n)。
(pairs nil))
(maphash (lambda (key count)
(push (cons key count) pairs))
table)
(let ((sorted (sort pairs #'> :key #'cdr)))
(subseq sorted 0 (min k (length sorted))))))Code language: Lisp (lisp)ボトルネックは頻度計算です。
そこをハッシュテーブルに変えるだけで O(n²) から O(n) になります。
あとは、ハッシュテーブルをペアリストに変換してソートします。
m = 異なる値の種類数とすると、m ≤ nで、ソートは O(m log m)。
通常は O(n + m log m) で十分ですが、バケットソートを使えばさらにソート部分も O(n) にできます。
(defun top-k-bucket (xs k)
"頻度の最大値が n を超えないことを利用してバケットソートする。"
(let* ((n (length xs))
(table (frequencies-fast xs))
(buckets (make-array (1+ n) :initial-element nil)))
(maphash (lambda (key count)
(push key (aref buckets count)))
table)
(let ((result nil)
(collected 0))
(loop for f from n downto 1 do
(dolist (key (aref buckets f))
(push (cons key f) result)
(incf collected)
(when (= collected k)
(return-from top-k-bucket (nreverse result)))))
(nreverse result))))Code language: Lisp (lisp)buckets[f] = 頻度 f の要素リスト。
4. 問題23 最長共通接頭辞
文字列のリスト strings を受け取り、すべての文字列に共通する最長の接頭辞を返す関数を書いてください。
入力: strings = ("flower" "flow" "flight")
出力: "fl"
入力: strings = ("interview" "interact" "interface")
出力: "inter"
入力: strings = ("dog" "racecar" "car")
出力: ""
入力: strings = ("abc" "abc" "abc")
出力: "abc"Code language: JavaScript (javascript)ファイルパスの共通ルートを求める、補完候補の共通部分を表示するなどの応用があります。subseq を毎回呼ぶ実装は余計なコピーを生みます。
問題21・22は「前処理した構造を後から使う」でした。
問題23は「どれだけコピーを避けるか」という観点で、「最後に1回だけ subseq する」設計が同じ精神を持ちます。
4.1. 素直な実装 — 文字列の切り詰めを繰り返す
(defun common-prefix-naive (strings)
"一致しなくなるたびに prefix を1文字ずつ縮める。"
(let ((prefix (copy-seq (first strings))))
(dolist (s (rest strings) prefix)
(loop while (and (> (length prefix) 0)
(not (string= prefix s
:end1 (min (length prefix) (length s))
:end2 (min (length prefix) (length s)))))
do (setf prefix (subseq prefix 0 (1- (length prefix))))))))Code language: Lisp (lisp)subseq で末尾を1文字ずつ切ると、毎回コピーが発生します。
4.2. 効く実装 — O(k × m)（k は文字列数、m は共通長）
subseq はコピーを生成します。
「何文字目まで共通か」という数だけを持ち回り、最後に1回だけコピーすることでコストを最小化できます。
(defun common-prefix-fast (strings)
"「何文字目まで共通か」をカウントして最後に1回だけ subseq する。"
(when strings
(let* ((first-str (first strings))
(limit (reduce #'min strings :key #'length))
(end 0))
(block find-end
(loop for i below limit do
(let ((ch (char first-str i)))
(if (every (lambda (s) (char= (char s i) ch))
(rest strings))
(incf end)
(return-from find-end)))))
(subseq first-str 0 end))))
;; 使用例
;; (common-prefix-fast '("flower" "flow" "flight")) => "fl"
;; (common-prefix-fast '("dog" "racecar" "car")) => ""Code language: Lisp (lisp)まずは、共通長の上限は最短文字列の長さです。
そこで、reduce :key #’length で全文字列の長さの最小値を求めます。
多重ループを使うので、抜けるために blockで名前付きブロックを作り、return-from でそこから抜けます。
中間コピーを避けて最後に1回という発想は Section 1 からの一貫したテーマです。
5. 問題24 リストの長さを何度も問い合わせる
整数のリスト lst を受け取り、「残りの要素数がリスト全体の半分未満になっている」尾部の個数を返す関数を書いてください。
入力: lst = (1 2 3 4 5 6) (全体長 6、半分 = 3)
出力: 3 ← 尾部 (4 5 6)(5 6)(6) の3つが長さ3未満
入力: lst = (1 2 3 4) (全体長 4、半分 = 2)
出力: 2 ← 尾部 (3 4)(4) の2つが長さ2未満
入力: lst = (1)
出力: 0Code language: HTTP (http)length を毎回ループ内で呼ぶと O(n²) になります。
全体長を1回だけ計算し、インデックス変数で残り長さを管理するだけで O(n) になります。
の締めくくりに、「前処理」の最もシンプルな形、つまりループ変数でインデックスを管理することを確認します。
5.1. 素直な実装 — O(n²)
loop for sub on lstでは、ストの各「尾部」を順に束縛します。
(defun count-short-prefixes-naive (lst)
(let ((total (length lst))
(count 0))
(loop for sub on lst do
(when (< (length sub) (/ total 2))
(incf count)))
count))Code language: Lisp (lisp)ただ、length を毎回呼んでいるので、O(|sub|)です。
5.2. 効く実装 — O(n)
残り長さは、 length を呼ばずに total – i で計算すれば、O(1)です。
(defun count-short-prefixes-fast (lst)
"インデックスで代用することで length の再計算を避ける。"
(let* ((total (length lst)) ; 一度だけ O(n)
(half (/ total 2))
(count 0)
(i 0))
(loop for sub on lst do
(incf i)
(when (< (- total i) half)
(incf count)))
count))Code language: PHP (php)length は O(n) です。
「ループの何周目か」はインデックス変数で O(1) に管理できます。
一度計算した値をループ内で使い回すという設計の最も単純な例です。
6. スライディングウィンドウ（問題 25〜28）
前処理によるクエリ高速化（問題20〜24）を確認した後、「連続する区間」に関する問題を扱います。
「全区間を試す」O(n²) または O(n³) の実装に対し、「右端を進めながら左端を必要に応じて動かす」スライディングウィンドウで O(n) になるパターンが共通しています。
7. 問題25 スライディングウィンドウの最大値
整数ベクタ vec と整数 k を受け取り、左端を1ずつずらしながら長さ k の各ウィンドウの最大値を順に返すリストを返す関数を書いてください。
入力: vec = #(1 3 -1 -3 5 3 6 7)
k = 3
出力: (3 3 5 5 6 7)
入力: vec = #(1 2 3 4 5)
k = 2
出力: (2 3 4 5)
入力: vec = #(9 8 7 6)
k = 4
出力: (9)Code language: PHP (php)毎回ウィンドウ内を走査すると O(nk) かかります。
単調デクを使えば O(n) になります。
AtCoder の「スライド最小値」問題でよく出てきます。
スライディングウィンドウの基本形として、ウィンドウ内の最大値を O(n) で求めます。
7.1. 素直な実装 — O(nk)
reduce #’max は :start :end で範囲を指定できます。
(defun window-max-naive (vec k)
"各ウィンドウで max を呼ぶ。"
(loop for i from 0 to (- (length vec) k)
collect (reduce #'max vec :start i :end (+ i k))))Code language: Lisp (lisp)7.2. 効く実装 — O(n)（単調デク）
単調デクは「ウィンドウ内で最大値になれない要素を即座に捨てる」発想です。
各要素はデクに1回追加されて1回削除されるので、n 個のウィンドウ全体で O(n) になります。
(defun window-max-fast (vec k)
"単調デク（monotone deque）を使う。"
(let ((n (length vec))
(deque '())
(result '()))
(loop for i from 0 below n do
(loop while (and deque (<= (car deque) (- i k)))
do (pop deque))
(loop while (and deque (<= (aref vec (car (last deque))) (aref vec i)))
do (setf deque (butlast deque)))
(setf deque (append deque (list i)))
(when (>= i (1- k))
(push (aref vec (car deque)) result)))
(nreverse result)))Code language: Lisp (lisp)dequeは、インデックスを格納する両端キューです。
先頭には、現在のウィンドウの最大値のインデックスを入れて、deque 内の値は単調減少になるように取ります。
要素 x の後に y > x が来たときに、x がウィンドウ内にいる間は常に y のほうが大きいため x は不要になります。
- Step 1：ウィンドウ外の先頭インデックスを除去。
- Step 2：末尾から、vec[後端] <= vec[i] の要素を除去。
- Step 3：i を末尾に追加。
- Step 4：ウィンドウが揃ったら先頭の最大値を記録。
8. 問題26 最長ユニーク部分文字列（スライディングウィンドウ応用）
文字列 s を受け取り、文字がすべて異なる連続部分文字列の長さの最大値を返す関数を書いてください。
入力: s = "abcabcbb"
出力: 3 ← "abc"
入力: s = "bbbbb"
出力: 1 ← "b"
入力: s = "pwwkew"
出力: 3 ← "wke"
入力: s = "abcde"
出力: 5 ← 文字列全体Code language: JavaScript (javascript)LeetCode Problem 3「Longest Substring Without Repeating Characters」に相当します。
全区間を試すと O(n²) または O(n³) ですが、スライディングウィンドウで O(n) になります。
問題25はウィンドウの幅が固定（k）でした。
問題26はウィンドウの幅が可変になります。
重複が起きたとき左端を飛ばすのがポイントです。
8.1. 素直な実装 — O(n³)
(defun longest-unique-naive (s)
"全部分文字列を試して重複チェックする。"
(let ((best 0)
(n (length s)))
(loop for i below n do
(loop for j from i below n do
(let ((seen (make-hash-table :test #'eql))
(ok t))
(loop for k from i to j do
(let ((ch (char s k)))
(if (gethash ch seen)
(setf ok nil)
(setf (gethash ch seen) t))))
(when ok
(setf best (max best (- j i -1)))))))
best))Code language: Lisp (lisp)8.2. 効く実装 — O(n) 期待値
「右端を進めながら左端を必要に応じて前進させる」スライディングウィンドウは、連続区間問題を O(n) にする典型手法です。
左端は後退しないため、全体の移動量が O(n) に収まります。
(defun longest-unique-fast (s)
"sliding window で左端を動かす。"
(let ((last-pos (make-hash-table :test #'eql))
(start 0)
(best 0))
(loop for i below (length s) do
(let* ((ch (char s i))
(prev (gethash ch last-pos -1)))
(when (>= prev start)
(setf start (1+ prev)))
(setf (gethash ch last-pos) i)
(setf best (max best (- i start -1)))))
best))
;; 使用例
;; (longest-unique-fast "abcabcbb") => 3 ("abc")
;; (longest-unique-fast "pwwkew") => 3 ("wke")Code language: Lisp (lisp)last-pos[ch] = ch の「最後に見たインデックス」。
start = ウィンドウの左端。
gethash の第3引数 -1 はデフォルト値（未登録なら -1）。
prev >= start なら、この文字はウィンドウ内で重複している。
start を prev+1 に飛ばして重複を排除する。
ウィンドウ長 = i – start + 1。
動作のトレース：
s = "abcabcbb"
i=0: ch=a, start=0, window="a", best=1
i=1: ch=b, start=0, window="ab", best=2
i=2: ch=c, start=0, window="abc", best=3
i=3: ch=a, prev=0 >= start=0 → start=1, window="bca", best=3
i=4: ch=b, prev=1 >= start=1 → start=2, window="cab", best=3
i=7: ch=b, prev=6 >= start=5 → start=7, window="b", best=3
=> 3Code language: JavaScript (javascript)9. 問題27 連続部分列の最大和（Kadane 法）
整数ベクタ vec を受け取り、連続する1つ以上の要素の和の最大値を返す関数を書いてください。
入力: vec = #(-2 1 -3 4 -1 2 1 -5 4)
出力: 6 ← [4 -1 2 1] の和
入力: vec = #(1 2 3 4 5)
出力: 15 ← 全体
入力: vec = #(-3 -1 -4 -1 -5)
出力: -1 ← 単要素 -1
入力: vec = #(5 -9 5)
出力: 5Code language: PHP (php)LeetCode Problem 53「Maximum Subarray」に相当します。
全区間を試すと O(n³)、前の和を使い回しても O(n²)、Kadane 法で O(n) になります。
問題25・26はウィンドウを滑らせる操作でした。
問題27では「ウィンドウの拡張と打ち切り」を動的に判断します。
動的計画法の入門例でもあります。
9.1. 素直な実装 — O(n³)
most-negative-fixnum：処理系が扱える最小の fixnum。「負の無限大」の代わり。
(defun max-subarray-naive (vec)
"全区間を試して毎回合計を計算する。"
(let ((best most-negative-fixnum))
(loop for i below (length vec) do
(loop for j from i below (length vec) do
(let ((sum 0))
;; 毎回 [i, j] の和を 0 から計算する。これが O(n³) の原因。
(loop for k from i to j do (incf sum (aref vec k)))
(when (> sum best) (setf best sum)))))
best))Code language: Lisp (lisp)前の区間の和を使い回す O(n²) 版：
(defun max-subarray-medium (vec)
(let ((best most-negative-fixnum))
(loop for i below (length vec) do
(let ((sum 0))
(loop for j from i below (length vec) do
(incf sum (aref vec j)) ; 前の sum を使い回す
(when (> sum best) (setf best sum)))))
best))Code language: JavaScript (javascript)9.2. 効く実装 — O(n)（Kadane 法）
O(n³) から O(n²)、O(n) と3段階の改善があります。
Kadane 法は「問題26のスライディングウィンドウ」と「後半の動的計画法（問題35〜）」をつなぐ橋渡しです。
直前の結果を持ち回るという発想が共通しています。
(defun max-subarray-kadane (vec)
"各位置で「ここで終わる最大和」だけを持つ。"
(let ((best (aref vec 0))
(current (aref vec 0)))
(loop for i from 1 below (length vec) do
(let ((x (aref vec i)))
(setf current (max x (+ current x)))
(setf best (max best current))))
best))
;; 使用例
;; (max-subarray-kadane #(-2 1 -3 4 -1 2 1 -5 4)) => 6 ([4 -1 2 1])
;; (max-subarray-kadane #(-1 -2 -3)) => -1 (全負のとき最大の単要素)Code language: Lisp (lisp)遷移：current = max(vec[i], current + vec[i])
→ 「今の要素単独」か「前の結果を延長する」かの大きいほうを選ぶ。
→ current が負になったらリセットするのと同じ意味。
DP の観点：
dp[i] = 「vec[i] を末尾に含む連続部分列の最大和」
初期：dp[0] = vec[0]
遷移：dp[i] = max(vec[i], dp[i-1] + vec[i])
答え：max over all i of dp[i]
dp テーブル全体は不要。
直前の値だけあれば済む → O(1) 空間。10. 問題28 2 Sum（スライディングウィンドウ的な発想）
整数ベクタ vec と整数 target を受け取り、和が target になる2要素のインデックスを (i j) の形で返す関数を書いてください。
必ず答えが1つ存在すると仮定します。
入力: vec = #(2 7 11 15)
target = 9
出力: (0 1) ← 2 + 7 = 9
入力: vec = #(3 2 4)
target = 6
出力: (1 2) ← 2 + 4 = 6
入力: vec = #(3 3)
target = 6
出力: (0 1)Code language: PHP (php)LeetCode Problem 1「Two Sum」に相当します。
全ペアを試すと O(n²)、ハッシュテーブルに「これまで見た値」を記録すれば O(n) になります。
問題11（最初の重複）で「視点の反転」を確認しました。
問題28はその応用です。
「2つの要素を探す」という問題を「1つ見たとき、もう一方がすでにあるか」に言い換えます。
10.1. 素直な実装 — O(n²)
(defun two-sum-naive (vec target)
"全ペアを試す。"
(let ((n (length vec)))
(loop for i from 0 below n do
(loop for j from (1+ i) below n do
(when (= (+ (aref vec i) (aref vec j)) target)
(return-from two-sum-naive (list i j)))))))Code language: Lisp (lisp)10.2. 効く実装 — O(n)
「2つを探す」問題を「1つを記録して、その補数を探す」に変換すると O(n) になります。
(defun two-sum-fast (vec target)
"ハッシュテーブルで補数を O(1) で検索する。"
(let ((seen (make-hash-table)))
(loop for i from 0 below (length vec) do
(let* ((x (aref vec i))
(complement (- target x))
(j (gethash complement seen)))
(when j
(return-from two-sum-fast (list j i)))
(setf (gethash x seen) i)))
nil))
;; 使用例
;; (two-sum-fast #(2 7 11 15) 9) => (0 1) (2 + 7 = 9)
;; (two-sum-fast #(3 2 4) 6) => (1 2) (2 + 4 = 6)Code language: Lisp (lisp) ;; 発想：vec[i] + vec[j] = target
;; ⟺ vec[j] = target – vec[i]
;; → vec[i] を見たとき「target – vec[i] を以前に見たか」を O(1) で確認。
;; x とそのインデックスを記録する。
問題11（重複検出）・問題12（フィルタ）・問題28（2Sum）は全員「ハッシュテーブルで補完情報を管理する」という同じ族です。