ホームページ >ウェブフロントエンド >jsチュートリアル >LeetCode: twoSum 問題
twoSum 問題は、問題解決能力とアルゴリズム スキルをテストする古典的なコーディングの課題です。
この投稿では、まず、理解しやすい簡単な解決策を見ていきます。次に、段階的に最適化して効率を向上させます。アルゴリズムを初めて使用する場合でも、面接の準備をしている場合でも、このガイドは問題を解決するのに役立ちます。始めましょう!
let inputArray = [2, 7, 11, 15] let target = 9 console.log(twoSum(inputArray, target)) // Output: [0, 1]
関数が処理する入力と出力を見てみましょう。
配列 [2,7,11,15] とターゲット 9 を指定すると、出力は [0,1] になります。
これは、インデックス 0 と 1 の値を合計すると、ターゲットである 9 になるためです。
function twoSum(nums, target) { const hashMap = {} }
配列内の数値をキーとして、そのインデックスを値として格納する hashMap を作成する解決策を考えます。
function twoSum(nums, target) { const hashMap = {} for (let i = 0; i < nums.length; i++) { hashMap[nums[i]] = i } }
これはソリューションの最初の部分です。hashMap の準備です。
次のループでは、配列内の現在の数値を引いたターゲットの補数が hashMap に含まれているかどうかを確認します。
function twoSum(nums, target) { const hashMap = {} for (let i = 0; i < nums.length; i++) { hashMap[nums[i]] = i } for (let i = 0; i < nums.length; i++) { const complement = target - nums[i] if (hashMap[complement] !== undefined && hashMap[complement] !== i) { return [i, hashMap[complement]] } } }
補数が hashMap で見つかった場合は、その値があるため、そのインデックスにアクセスできます。
次に、現在の反復を表す i とともにその値 (補数のインデックス) を含む配列を返すことができます。
このソリューションでは、2 つの別々のループを作成していることがわかります。それらを 1 つのループに結合することで、1 回の反復を節約できます。
function twoSum(nums, target) { const hashMap = {} for (let i = 0; i < nums.length; i++) { const complement = target - nums[i] if (hashMap[complement] !== undefined && hashMap[complement] !== i) { return [i, hashMap[complement]] } hashMap[nums[i]] = i } }
より明確にするために条件を改良し、次のコードを取得しました:
function twoSum(nums, target) { const hashMap = {} for (let i = 0; i < nums.length; i++) { const complement = target - nums[i] if (complement in hashMap) { return [i, hashMap[complement]] } hashMap[nums[i]] = i } } let inputArray = [2, 7, 11, 15] let target = 9 console.log(twoSum(inputArray, target)) // Output: [0, 1]
以上がLeetCode: twoSum 問題の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。