フェアペアの数を数える

2563。フェアペアの数を数えます

難易度: 中

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

サイズ n と上下 2 つの整数の 0 インデックス付き 整数配列 num を指定すると、公平なペアの数を返します。

次の場合、ペア (i, j) は 公正です。

• 0
• 下側

例 1:

• 入力: 数値 = [0,1,7,4,4,5]、下位 = 3、上位 = 6
• 出力: 6
• 説明: 6 つの公平なペアがあります: (0,3)、(0,4)、(0,5)、(1,3)、(1,4)、および (1,5) .

例 2:

• 入力: 数値 = [1,7,9,2,5]、下位 = 11、上位 = 11
• 出力: 1
• 説明: 単一の公平なペアがあります: (2,3)。

制約:

• 1 5
• nums.length == n
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= 下 <= 上 <= 10⁹

ヒント:

1. 配列を昇順に並べ替えます。
2. 配列内の各数値について、この数値と公正なペアを形成できる配列内の最小の数値と最大の数値を追跡します。
3. 大きな数値に移動すると、両方の境界が下に移動します。

解決策:

次のアプローチを使用できます:

1. 配列の並べ替え: 並べ替えは、2 ポインター手法を活用し、バイナリ検索をより効果的に実行するのに役立ちます。
2. ツーポインター手法: ソートされた配列内の各要素について、その要素と公正なペアを形成できる要素の範囲を計算できます。この範囲を見つけるには二分探索を使用します。
3. 境界の二分探索: 各要素 nums[i] について、j > の範囲 [ lower, upper] - nums[i] を見つけます。私。二分探索を使用して、この範囲を満たす最小および最大のインデックスを見つけます。

このソリューションを PHP で実装してみましょう: 2563。フェアペアの数を数えます

  
  
  説明：




並べ替え: 二分探索で有効なペアを見つけやすくするために、配列 nums を並べ替えます。

二分探索境界:


各要素 nums[i] について、合計が収まる範囲となる下限値と上限値を見つけます。
2 つの二分検索を使用して、nums[i] nums[j] が [lower, upper] 内に収まるインデックスの範囲 [left, right) を見つけます。



ペアのカウント: 各 i の左と右の間の有効なインデックスの数を追加します。


このアプローチの時間計算量は、各要素の並べ替えと二分探索のため O(n log n) であり、大規模な入力に対して十分効率的です。

連絡先リンク

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

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


LinkedIn
GitHub



          

            
  

            
        
以上がフェアペアの数を数えるの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。