JavaScript の 2 つの和の問題

Dec 28, 2024 am 06:35 AM

Two Sum problem in Javascript

一般的な考え方

Two Sum 問題は、古典的なアルゴリズムの問​​題です。これは、指定された特定の *ターゲット * に合計される 2 つの数値を配列内で見つけて、指定された配列からそれらのインデックスを返すように求めます。

問題提起

整数 nums の配列と整数ターゲットが与えられた場合、合計がターゲットになるように 2 つの数値のインデックスを返します。各入力にはソリューションが 1 つだけあり、同じ要素を 2 回使用することはできません。

入力: 数値 = [2, 7, 11, 15]、ターゲット = 9
出力: [0, 1]
説明: nums[0] nums[1] = 2 7 = 9

アプローチ 1 ブルートフォース

どんな問題でも最初のアプローチは、何かを成し遂げること、そして概念的に最も簡単なことを実行することかもしれません。

2 つのループで配列を反復処理し、数値のすべてのペアをチェックします。

const twoSum = (nums, target) => {
  for(let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      console.log(` i is ${nums[i]} and k is ${nums[j]}`)
      // lets check if we add the 2 numbers if it equals target
      if (target === nums[i] + nums[j]) {
        return [i, j]
      }
    }
  }
};

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSum(nums, target));

ログイン後にコピー

アプローチ 1 複雑さ

時間計算量O(n²)

  1. すべての数値ペアをチェックする入れ子ループ
  2. 可能なすべての組み合わせをチェックします
  3. 配列が大きいと非常に遅くなります

空間の複雑さO(1)
1.新しいデータ構造は作成していません

アプローチ 2 より効率的で、私たちが望んでいること。

これを解決するためにハッシュ マップを使用します。このアルゴリズムについて少し説明しましょう

  1. 見た数値を保存するためにハッシュ マップ (JavaScript のオブジェクト) を使用します
  2. 各数値について、その補数 (ターゲット - 現在の数値) を計算します
  3. マップ内に補体が存在するかどうかを確認します
  4. そうであれば、2 つの数値が見つかり、それらのインデックスが返されます
  5. そうでない場合は、現在の番号をマップに追加します

最初の解決策は、通常の JS オブジェクトを使用し、その方法で HashMap を構築することです

const twoSumOptimizedRegularObject = (nums, target) => {
  const objectStuff = {}

  // write a for loop, to go through the arr
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i] 

    if (complement in objectStuff) {
      return [objectStuff[complement],i]
    }
    objectStuff[nums[i]] = i 
  }
}

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSumOptimizedRegularObject(nums, target));

ログイン後にコピー

2 番目の解決策は、実際には JS で Map データ構造を使用することです。これにより、Map オブジェクト (ES6 で導入) を使用して、より厳密で堅牢な実装が可能になり、多くの場合好まれます。 Map は明示的なハッシュ マップの動作を提供し、Object.prototype.
からのプロパティの継承など、JavaScript オブジェクトのいくつかの特殊な動作を回避します。

const twoSumOptimized = (nums, target) => {
  const mapOfStuff = new Map()

  // write a for loop, to go through the arr
  for (let i = 0; i < nums.length; i++) {
    let complement = target - nums[i]

    if (mapOfStuff.has(complement)) {
      return [mapOfStuff.get(complement), i]
    }
    mapOfStuff.set(nums[i], i)
  }

}

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSumOptimized(nums, target));

ログイン後にコピー

アプローチ 2 複雑さ

時間計算量O(n)

  1. 配列を単一パスで通過
  2. ハッシュ マップは O(1) ルックアップを提供します
  3. 合計時間は配列サイズに比例して増加します

空間の複雑さ は O(n)
最悪の場合、ほぼすべての数値が保存される可能性があります
時間とメモリ効率のトレードオフ

注意事項

  1. 空の配列
  2. 解決策は存在しません
  3. 複数の解決策が可能です。この場合、最初の反復後に戻るかどうかを尋ねます。

以上がJavaScript の 2 つの和の問題の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

このウェブサイトの声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

Video Face Swap

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

メモ帳++7.3.1

メモ帳++7.3.1

使いやすく無料のコードエディター

SublimeText3 中国語版

SublimeText3 中国語版

中国語版、とても使いやすい

ゼンドスタジオ 13.0.1

ゼンドスタジオ 13.0.1

強力な PHP 統合開発環境

ドリームウィーバー CS6

ドリームウィーバー CS6

ビジュアル Web 開発ツール

SublimeText3 Mac版

SublimeText3 Mac版

神レベルのコード編集ソフト(SublimeText3)

フロントエンドのサーマルペーパーレシートのために文字化けしたコード印刷に遭遇した場合はどうすればよいですか? フロントエンドのサーマルペーパーレシートのために文字化けしたコード印刷に遭遇した場合はどうすればよいですか? Apr 04, 2025 pm 02:42 PM

フロントエンドのサーマルペーパーチケット印刷のためのよくある質問とソリューションフロントエンド開発におけるチケット印刷は、一般的な要件です。しかし、多くの開発者が実装しています...

javascriptの分解:それが何をするのか、なぜそれが重要なのか javascriptの分解:それが何をするのか、なぜそれが重要なのか Apr 09, 2025 am 12:07 AM

JavaScriptは現代のWeb開発の基礎であり、その主な機能には、イベント駆動型のプログラミング、動的コンテンツ生成、非同期プログラミングが含まれます。 1)イベント駆動型プログラミングにより、Webページはユーザー操作に応じて動的に変更できます。 2)動的コンテンツ生成により、条件に応じてページコンテンツを調整できます。 3)非同期プログラミングにより、ユーザーインターフェイスがブロックされないようにします。 JavaScriptは、Webインタラクション、シングルページアプリケーション、サーバー側の開発で広く使用されており、ユーザーエクスペリエンスとクロスプラットフォーム開発の柔軟性を大幅に改善しています。

誰がより多くのPythonまたはJavaScriptを支払われますか? 誰がより多くのPythonまたはJavaScriptを支払われますか? Apr 04, 2025 am 12:09 AM

スキルや業界のニーズに応じて、PythonおよびJavaScript開発者には絶対的な給与はありません。 1. Pythonは、データサイエンスと機械学習でさらに支払われる場合があります。 2。JavaScriptは、フロントエンドとフルスタックの開発に大きな需要があり、その給与もかなりです。 3。影響要因には、経験、地理的位置、会社の規模、特定のスキルが含まれます。

JavaScriptを使用して、同じIDを持つArray要素を1つのオブジェクトにマージする方法は? JavaScriptを使用して、同じIDを持つArray要素を1つのオブジェクトにマージする方法は? Apr 04, 2025 pm 05:09 PM

同じIDを持つ配列要素をJavaScriptの1つのオブジェクトにマージする方法は?データを処理するとき、私たちはしばしば同じIDを持つ必要性に遭遇します...

JavaScriptは学ぶのが難しいですか? JavaScriptは学ぶのが難しいですか? Apr 03, 2025 am 12:20 AM

JavaScriptを学ぶことは難しくありませんが、挑戦的です。 1)変数、データ型、関数などの基本概念を理解します。2)非同期プログラミングをマスターし、イベントループを通じて実装します。 3)DOM操作を使用し、非同期リクエストを処理することを約束します。 4)一般的な間違いを避け、デバッグテクニックを使用します。 5)パフォーマンスを最適化し、ベストプラクティスに従ってください。

Shiseidoの公式Webサイトのように、視差スクロールと要素のアニメーション効果を実現する方法は?
または:
Shiseidoの公式Webサイトのようにスクロールするページを伴うアニメーション効果をどのように実現できますか? Shiseidoの公式Webサイトのように、視差スクロールと要素のアニメーション効果を実現する方法は? または: Shiseidoの公式Webサイトのようにスクロールするページを伴うアニメーション効果をどのように実現できますか? Apr 04, 2025 pm 05:36 PM

この記事の視差スクロールと要素のアニメーション効果の実現に関する議論では、Shiseidoの公式ウェブサイト(https://www.shisido.co.co.jp/sb/wonderland/)と同様の達成方法について説明します。

JavaScriptの進化:現在の傾向と将来の見通し JavaScriptの進化:現在の傾向と将来の見通し Apr 10, 2025 am 09:33 AM

JavaScriptの最新トレンドには、TypeScriptの台頭、最新のフレームワークとライブラリの人気、WebAssemblyの適用が含まれます。将来の見通しは、より強力なタイプシステム、サーバー側のJavaScriptの開発、人工知能と機械学習の拡大、およびIoTおよびEDGEコンピューティングの可能性をカバーしています。

Console.log出力の違い結果:なぜ2つの呼び出しが異なるのですか? Console.log出力の違い結果:なぜ2つの呼び出しが異なるのですか? Apr 04, 2025 pm 05:12 PM

Console.log出力の違いの根本原因に関する詳細な議論。この記事では、Console.log関数の出力結果の違いをコードの一部で分析し、その背後にある理由を説明します。 �...

See all articles