問題概要
整数の配列と、特定の目標合計値が与えられます。この配列の中から、2つの異なる要素を選び、それらの合計が目標合計値と一致するような2つの要素のインデックスを返す関数を実装してください。各入力に対して正確に1つの解が存在すると仮定し、また同じ要素を2度使用することはできません。
例
入力: データ = [3, 5, 8, 12], 目標値 = 13
データ[1] (5) + データ[2] (8) = 13
したがって、結果はインデックスのペア [1, 2] となります。
主要なアルゴリズムとアプローチ
この一般的なプログラミング問題には、いくつかの異なる解決策が存在し、それぞれが特定のシナリオでのパフォーマンス要件に応じて選択されます。
1. ハッシュマップを用いた高速探索 (One-Pass Hash Map)
この手法では、配列を一度だけ走査します。各数値 N を処理する際、ターゲット値 - N が既にハッシュマップに存在するかを確認します。もし存在すれば、その要素と現在の要素が目標合計を形成するため、それぞれのインデックスを直ちに返します。存在しない場合は、現在の数値 N とそのインデックスをハッシュマップに追加します。これにより、各要素を一度しか見ないため、非常に効率的です。
Go言語による実装
package main
// findSumPairIndices は、与えられた配列から合計がtargetSumになる2つの要素のインデックスを返します。
// 各要素は一度しか使用できません。
func findSumPairIndices(data []int, targetSum int) []int {
seenValues := make(map[int]int) // 値とそのインデックスを格納するマップ
for currentIdx, currentValue := range data {
requiredValue := targetSum - currentValue // 目標合計を達成するために必要な値
// requiredValueが既にマップに存在するかを確認
if existingIdx, found := seenValues[requiredValue]; found {
// 存在する場合、見つかったインデックスと現在のインデックスのペアを返す
return []int{existingIdx, currentIdx}
}
// requiredValueが見つからなかった場合、現在の値とそのインデックスをマップに追加
seenValues[currentValue] = currentIdx
}
return nil // 問題の制約により、ここに到達することはないはず (必ず解が見つかるため)
}
C++による実装
#include <vector>
#include <unordered_map> // ハッシュマップ用
class ArraySearch {
public:
// locateTargetSum は、numbers配列から合計がsumTargetになる2つの要素のインデックスを見つけます。
std::vector<int> locateTargetSum(const std::vector<int>& numbers, int sumTarget) {
std::unordered_map<int, int> valueToIndexMap; // {数値: インデックス} を格納
for (int currentIndex = 0; currentIndex < numbers.size(); ++currentIndex) {
int currentNum = numbers[currentIndex];
int requiredComplement = sumTarget - currentNum; // 補数を計算
// 補数がマップに存在するかをチェック
if (valueToIndexMap.count(requiredComplement)) {
// 存在する場合、そのインデックスと現在のインデックスを返す
return {valueToIndexMap.at(requiredComplement), currentIndex};
}
// 補数が見つからなかった場合、現在の数値とそのインデックスをマップに追加
valueToIndexMap[currentNum] = currentIndex;
}
return {}; // 解が見つからない場合 (問題の制約により、通常は到達しない)
}
};
アルゴリズム分析
- 時間計算量 (Time Complexity): O(n)。配列を一度だけ走査し、ハッシュマップの操作（挿入、検索）は平均でO(1)であるため、全体として線形時間で動作します。
- 空間計算量 (Space Complexity): O(n)。最悪の場合、ハッシュマップに全ての要素が格納されるため、O(n)の追加空間が必要です。
2. ソートと2ポインタ法 (Sorting and Two-Pointers)
このアプローチでは、元の配列の要素とその元のインデックスのペアを作成し、そのペアを要素の値に基づいて昇順にソートします。次に、ソートされた配列の両端から2つのポインタ（左と右）を開始します。左ポインタは配列の先頭、右ポインタは末尾を指します。両ポインタが交差しない限り、ポインタが指す値の合計を計算し、目標値と比較します。
- 合計が目標値と等しい場合、対応する元のインデックスを返します。
- 合計が目標値より小さい場合、
左ポインタを右に移動して合計を増やします。 - 合計が目標値より大きい場合、
右ポインタを左に移動して合計を減らします。
Go言語による実装
package main
import (
"sort"
)
// ElementWithOriginalIndex は、元の配列の要素とそのインデックスを保持します。
type ElementWithOriginalIndex struct {
Val int
OriginalIdx int
}
// findSumPairBySorting は、ソートと2ポインタ法を使用して合計がtargetSumになる2つの要素のインデックスを返します。
func findSumPairBySorting(inputSlice []int, targetSum int) []int {
// 要素と元のインデックスのペアを作成
indexedElements := make([]ElementWithOriginalIndex, len(inputSlice))
for i, num := range inputSlice {
indexedElements[i] = ElementWithOriginalIndex{Val: num, OriginalIdx: i}
}
// 要素の値に基づいて昇順にソート
sort.Slice(indexedElements, func(i, j int) bool {
return indexedElements[i].Val < indexedElements[j].Val
})
// 2つのポインタを初期化
ptrLeft, ptrRight := 0, len(indexedElements)-1
// ポインタが交差するまで探索を続ける
for ptrLeft < ptrRight {
currentCombinedSum := indexedElements[ptrLeft].Val + indexedElements[ptrRight].Val
if currentCombinedSum == targetSum {
// 目標合計と一致する場合、元のインデックスを返す
return []int{indexedElements[ptrLeft].OriginalIdx, indexedElements[ptrRight].OriginalIdx}
} else if currentCombinedSum < targetSum {
// 合計が目標より小さい場合、左ポインタを右へ移動
ptrLeft++
} else {
// 合計が目標より大きい場合、右ポインタを左へ移動
ptrRight--
}
}
return nil // 解が見つからない場合
}
C++による実装
#include <vector>
#include <algorithm> // sort用
#include <utility> // pair用
class ArrayFinder {
public:
// findPairUsingTwoPointers は、ソートと2ポインタ法でターゲット合計に一致するインデックスを検索します。
std::vector<int> findPairUsingTwoPointers(const std::vector<int>& inputData, int sumTarget) {
// 値とその元のインデックスをペアで保持するベクタ
std::vector<std::pair<int, int>> indexedValues;
indexedValues.reserve(inputData.size()); // メモリ割り当てを最適化
for (int i = 0; i < inputData.size(); ++i) {
indexedValues.emplace_back(inputData[i], i);
}
// 値に基づいてペアをソート
std::sort(indexedValues.begin(), indexedValues.end());
int startPtr = 0;
int endPtr = indexedValues.size() - 1;
// 2ポインタで探索
while (startPtr < endPtr) {
int currentCombinedSum = indexedValues[startPtr].first + indexedValues[endPtr].first;
if (currentCombinedSum == sumTarget) {
// 合計が一致したら、元のインデックスを返す
return {indexedValues[startPtr].second, indexedValues[endPtr].second};
} else if (currentCombinedSum < sumTarget) {
// 合計が小さすぎる場合、左ポインタをインクリメント
++startPtr;
} else {
// 合計が大きすぎる場合、右ポインタをデクリメント
--endPtr;
}
}
return {}; // 解が見つからない場合
}
};
アルゴリズム分析
- 時間計算量 (Time Complexity): O(n log n)。配列のソートにO(n log n)かかり、その後の2ポインタによる走査はO(n)であるため、全体としてソートのコストが支配的です。
- 空間計算量 (Space Complexity): O(n)。元のインデックスを保持するための追加の配列（またはベクタ）が必要となります。
3. 総当たり法 (Brute Force)
この最も直接的な方法は、配列内の考えられるすべての数値の組み合わせを試します。2つのネストされたループを使用して、各要素のペアを順に調べます。各ペアについて、それらの合計が目標値と一致するかどうかを比較します。一致するペアが見つかった場合、その要素のインデックスを返します。シンプルですが、大規模なデータセットでは非効率です。
Go言語による実装
package main
// findSumBruteForce は、総当たり法を使用して合計がtargetValueになる2つの要素のインデックスを返します。
func findSumBruteForce(numbers []int, targetValue int) []int {
// 最初の要素から順に選択
for outerIdx := 0; outerIdx < len(numbers); outerIdx++ {
// 最初の要素の次から、残りの要素を選択
for innerIdx := outerIdx + 1; innerIdx < len(numbers); innerIdx++ {
// 2つの要素の合計が目標値と一致するかをチェック
if numbers[outerIdx]+numbers[innerIdx] == targetValue {
return []int{outerIdx, innerIdx} // 一致した場合、インデックスを返す
}
}
}
return nil // 解が見つからない場合
}
C++による実装
#include <vector>
class SimpleSumFinder {
public:
// findPairBruteForce は、総当たり法でターゲット合計に一致するインデックスを検索します。
std::vector<int> findPairBruteForce(const std::vector<int>& inputNums, int desiredSum) {
// 最初のインデックスを0から開始
for (int firstIdx = 0; firstIdx < inputNums.size(); ++firstIdx) {
// 2番目のインデックスを最初のインデックスの次から開始
for (int secondIdx = firstIdx + 1; secondIdx < inputNums.size(); ++secondIdx) {
// 2つの要素の合計が希望する合計値に等しいかチェック
if (inputNums[firstIdx] + inputNums[secondIdx] == desiredSum) {
return {firstIdx, secondIdx}; // 一致した場合、インデックスのペアを返す
}
}
}
return {}; // 解が見つからない場合
}
};
アルゴリズム分析
- 時間計算量 (Time Complexity): O(n^2)。ネストされた2つのループにより、最悪の場合、すべての要素の組み合わせをチェックする必要があるため、二乗の時間計算量となります。
- 空間計算量 (Space Complexity): O(1)。追加のデータ構造は必要なく、定数レベルの空間しか使用しません。
4. 二分探索法 (Binary Search)
この方法もソートを前処理として含みますが、その後の探索アプローチが異なります。まず、元の配列の要素とインデックスのペアを作成し、値を基準にソートします。次に、ソートされた配列の各要素 A について、ターゲット値 - A となる補数 B を見つけるために、残りの部分配列に対して二分探索を実行します。補数 B が見つかった場合、両方の要素の元のインデックスが異なることを確認し、それらを返します。
Go言語による実装
package main
import (
"sort"
)
// findSumWithBinarySearch は、二分探索法を使用して合計がgoalになる2つの要素のインデックスを返します。
func findSumWithBinarySearch(elements []int, goal int) []int {
// 元のインデックスを保持し、ソート時に要素の値で並べ替えるためのスライス
sortedOriginalIndices := make([]int, len(elements))
for i := range elements {
sortedOriginalIndices[i] = i
}
// 元の配列の要素の値に基づいて、インデックスのスライスをソート
sort.Slice(sortedOriginalIndices, func(i, j int) bool {
return elements[sortedOriginalIndices[i]] < elements[sortedOriginalIndices[j]]
})
// 各要素について補数を二分探索で探す
for currentPtr := 0; currentPtr < len(elements); currentPtr++ {
currentElementOriginalIdx := sortedOriginalIndices[currentPtr]
neededValue := goal - elements[currentElementOriginalIdx] // 補数
// 残りの部分配列（currentPtrの次から）で二分探索を実行
searchLeft, searchRight := currentPtr+1, len(elements)-1
for searchLeft <= searchRight {
searchMid := searchLeft + (searchRight-searchLeft)/2
midElementOriginalIdx := sortedOriginalIndices[searchMid]
if elements[midElementOriginalIdx] == neededValue {
return []int{currentElementOriginalIdx, midElementOriginalIdx}
} else if elements[midElementOriginalIdx] < neededValue {
searchLeft = searchMid + 1
} else {
searchRight = searchMid - 1
}
}
}
return nil // 解が見つからない場合
}
C++による実装
#include <vector>
#include <algorithm> // sort用
#include <numeric> // iota用
class BinarySearchSumFinder {
public:
// findPairUsingBinarySearch は、二分探索法でターゲット値になるペアのインデックスを検索します。
std::vector<int> findPairUsingBinarySearch(const std::vector<int>& inputArr, int targetVal) {
// 元のインデックスを保存し、そのインデックスを基にinputArrの値をソートする
std::vector<int> sortedOriginalIndices(inputArr.size());
std::iota(sortedOriginalIndices.begin(), sortedOriginalIndices.end(), 0); // 0, 1, 2, ... で初期化
// inputArrの要素の値に基づいてインデックスをソート
std::sort(sortedOriginalIndices.begin(), sortedOriginalIndices.end(),
[&inputArr](int i, int j) { return inputArr[i] < inputArr[j]; });
// 各要素を繰り返し、補数を二分探索で探す
for (int i = 0; i < inputArr.size(); ++i) {
int currentOriginalIndex = sortedOriginalIndices[i];
int requiredComplement = targetVal - inputArr[currentOriginalIndex];
// 現在の要素の次から右側で二分探索を実行
int searchStart = i + 1;
int searchEnd = inputArr.size() - 1;
while (searchStart <= searchEnd) {
int searchMid = searchStart + (searchEnd - searchStart) / 2;
int midElementOriginalIndex = sortedOriginalIndices[searchMid];
if (inputArr[midElementOriginalIndex] == requiredComplement) {
// 補数が見つかった場合、元のインデックスを返す
return {currentOriginalIndex, midElementOriginalIndex};
} else if (inputArr[midElementOriginalIndex] < requiredComplement) {
searchStart = searchMid + 1;
} else {
searchEnd = searchMid - 1;
}
}
}
return {}; // 解が見つからない場合
}
};
アルゴリズム分析
- 時間計算量 (Time Complexity): O(n log n)。ソートにO(n log n)、各要素に対する二分探索はO(log n)で、それがn回繰り返されるため、全体としてO(n log n)となります。
- 空間計算量 (Space Complexity): O(n)。元のインデックスを保存するための追加の配列（またはベクタ）が必要となります。