モダンJavaScript入門: ハッシュマップを用いて配列内の2つの数の合計が特定の値になる組み合わせを見つける

1. はじめに

この記事では、JavaScriptのハッシュマップを用いて、配列内の2つの数の合計が特定の値になる組み合わせを見つける方法を解説します。

2. ハッシュマップとは

ハッシュマップは、キーと値のペアを保存するためのデータ構造です。JavaScriptでは、オブジェクトという形でハッシュマップを利用することができます。

3. 問題の説明

配列内の2つの数値の合計が特定の値となる組み合わせを見つける問題を考えます。例えば、配列[2, 7, 11, 15]と目標値9が与えられた場合、2と7の合計が9となるため、そのインデックス[0, 1]が答えとなります。

4. 解法詳細

ここでハッシュマップが役立ちます。配列を左から右に一度だけスキャンしながら、各要素について、目標値からその要素を引いた値がハッシュマップに存在するかどうかをチェックします。もし存在すれば、その組み合わせが答えとなります。

5. コード例

function twoSum(nums, target) {
    let map = {};
    for (let i = 0; i < nums.length; i++) {
        let complement = target - nums[i];
        if (map[complement] !== undefined) {
            return [map[complement], i];
        }
        map[nums[i]] = i;
    }
    return null;
}
console.log(twoSum([2, 7, 11, 15], 9));  // Output: [0, 1]

6. 応用例

このアプローチは、他の問題にも応用できます。例えば、配列内の3つの数値の合計が特定の値となる組み合わせを見つける問題などです。

応用例1

3つの数値の合計が目標値となる組み合わせを見つける。

function threeSum(nums, target) {
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length - 2; i++) {
        let left = i + 1, right = nums.length - 1;
        while (left < right) {
            let sum = nums[i] + nums[left] + nums[right];
            if (sum === target) {
                return [i, left, right];
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    return null;
}
console.log(threeSum([1, 2, 7, 11, 15], 20));  // Output: [1, 2, 4]

応用例2

配列内の数値の合計が目標値となる全ての組み合わせを見つける。

function combinationSum(candidates, target) {
    let result = [];
    candidates.sort((a, b) => a - b);
    backtrack(result, [], candidates, target, 0);
    return result;
}

function backtrack(result, track, candidates, target, start) {
    if (target < 0) {
        return;
    } else if (target === 0) {
        result.push(track.slice());
        return;
    } else {
        for (let i = start; i < candidates.length; i++) {
            track.push(candidates[i]);
            backtrack(result, track, candidates, target - candidates[i], i);
            track.pop();
        }
    }
}
console.log(combinationSum([2, 3, 6, 7], 7));  // Output: [[2, 2, 3], [7]]

7. まとめ

この記事では、JavaScriptでハッシュマップを使って、特定の合計値を持つ配列内の数値のペアを見つける方法を学びました。また、その応用例として、3つの数値の合計や、目標値となる全ての組み合わせを見つける方法も見てきました。

AIko Code Symphony