問題概要
配列内の2つの要素を選択し、その和が指定された値に一致する組み合わせを高速に見つける。配列は少なくとも1組の解を持つことが保証されている。
例：配列 [5, 6, 1, 4, 7, 8, 9]、目標値 10
解法1：全探索（二重ループ）
すべてのペアを試す方法。時間計算量は O(N²) であり、効率が低い。
<pre>
#include <iostream>
using namespace std;
void findPair(int* arr, int size) {
for (int i = 0; i < size - 1; ++i) {
for (int j = i + 1; j < size; ++j) {
if (arr[i] + arr[j] == 10) {
cout << "数: " << arr[i] << ", " << arr[j] << endl;
}
}
}
}
int main() {
int data[] = {5, 6, 1, 4, 7, 8, 9};
int len = sizeof(data) / sizeof(data[0]);
findPair(data, len);
return 0;
}
</pre>
解法2：ソート + 二分探索
配列をソートした後、各要素に対して target - current の値が存在するかを二分探索で確認。全体の時間計算量は O(N log N)。
解法3：両端から収束するアプローチ（最適）
ソート済み配列に対して、左端と右端から指標を動かしながら合計を調整。和が目標より大きい場合は右側を縮小、小さい場合は左側を拡大。一度の走査で全組み合わせを検出可能。時間計算量 O(N log N)（主にソートによるコスト）。
<pre>
#include <iostream>
#include <algorithm>
using namespace std;
void findTwoSum(int* arr, int size) {
int left = 0, right = size - 1;
while (left < right) {
int total = arr[left] + arr[right];
if (total == 10) {
cout << arr[left] << ", " << arr[right] << endl;
left++;
} else if (total < 10) {
left++;
} else {
right--;
}
}
}
int main() {
int data[] = {5, 6, 1, 4, 7, 8, 9};
sort(data, data + 7);
int len = sizeof(data) / sizeof(data[0]);
findTwoSum(data, len);
return 0;
}
</pre>
拡張：3数和問題
3つの数の和が指定値になる組み合わせを求める。固定する要素を1つ選び、残り2つについて両端からの探索を行う。
例：目標値 17 に対する解
<pre>
#include <iostream>
#include <algorithm>
using namespace std;
void findThreeSum(int* arr, int size) {
for (int k = 0; k < size - 2; ++k) {
int i = k + 1;
int j = size - 1;
while (i < j) {
int sum = arr[k] + arr[i] + arr[j];
if (sum == 17) {
cout << arr[k] << ", " << arr[i] << ", " << arr[j] << endl;
i++;
} else if (sum < 17) {
i++;
} else {
j--;
}
}
}
}
int main() {
int data[] = {5, 6, 1, 4, 7, 8, 9};
sort(data, data + 7);
int len = sizeof(data) / sizeof(data[0]);
findThreeSum(data, len);
return 0;
}
</pre>
この手法は一般化可能で、4数和やそれ以上の多項和に対しても同様の戦略が適用できる。