N とその double が存在するかどうかを確認する

1346。 N とその double が存在するかどうかを確認します

難易度: 簡単

トピック: 配列、ハッシュ テーブル、2 つのポインター、二分探索、並べ替え

整数の配列 arr が与えられた場合、次のような 2 つのインデックス i と j が存在するかどうかを確認します。

• i != j
• 0
• arr[i] == 2 * arr[j]

例 1:

• 入力: arr = [10,2,5,3]
• 出力: true
• 説明: i = 0 および j = 2 の場合、arr[i] == 10 == 2 * 5 == 2 * arr[j]

例 2:

• 入力: arr = [3,1,7,11]
• 出力: false
• 説明: 条件を満たす i と j がありません。

制約:

• 2
• -10³ <= arr[i] <= 10³

ヒント:

1. i = 0 から arr.length までループし、[0, i - 1] からの配列要素を hashTable に維持します。
2. ループの各ステップで、これまでに要素 2 * arr[i] が見つかったかどうかを確認します。
3. arr[i] % 2 == 0 の場合に arr[i] / 2 が確認されたかどうかも確認します。

解決策:

ハッシュ テーブル (連想配列) を使用して、配列の反復処理中にすでに検出された要素を追跡できます。このアイデアは、各要素 arr[i] について、その倍値 (つまり、2 * arr[i]) または半分 (つまり、偶数の場合は arr[i] / 2) がすでに検出されているかどうかをチェックすることです。

段階的な解決策は次のとおりです:

プラン：

1. 配列を反復処理します。
2. 各要素 arr[i] について、ハッシュ テーブル内に 2 * arr[i] または arr[i] / 2 (arr[i] が偶数の場合) があるかどうかを確認します。
3. いずれかの条件が満たされた場合、true を返します。
4. それ以外の場合は、arr[i] をハッシュ テーブルに追加し、次の要素に進みます。
5. 最後まで一致するものが見つからなかった場合は false を返します。

このソリューションを PHP で実装してみましょう: 1346。 N とその double が存在するかどうかを確認します

説明：

1. ハッシュ テーブル: $hashTable 連想配列を使用して、これまでに遭遇した要素を保存します。
2. 最初の条件: 各要素 arr[i] について、arr[i] * 2 がハッシュ テーブルに存在するかどうかを確認します。
3. 2 番目の条件: 要素が偶数の場合、arr[i] / 2 がハッシュ テーブルに存在するかどうかを確認します。
4. ハッシュ テーブルへの追加: チェック後、今後の参照のために arr[i] をハッシュ テーブルに追加します。
5. Return: 一致するものが見つかった場合は、すぐに true を返します。ループ後に一致するものが見つからない場合は、false を返します。

時間計算量:

• 時間計算量は O(n) です。ここで、n は配列の長さです。これは、各要素が 1 回処理され、ハッシュ テーブル内の要素の確認や追加には平均して一定の時間がかかるためです。

空間の複雑さ:

• ハッシュ テーブルに必要なストレージのため、スペースの複雑さは O(n) です。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上がN とその double が存在するかどうかを確認するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。