指定された製品でペアを確認してください
GFG練習で試してみてください 
出力
出力
出力
配列が与えられます arr [] の n 明確な整数とa ターゲット 値は、製品がターゲットに等しいものであるアレイに一対の要素があるかどうかを確認することです。
例：
入力： arr [] = [1 5 7 -1 5]ターゲット= 35
出力： 真実
説明： 5* 7 = 35として、答えは真です。入力： arr [] = [-10 20 9 -40]ターゲット= 30
出力： 間違い
説明： 製品30にはペアが存在しません
コンテンツの表
- 可能なすべてのペアを生成することにより、[ナイーブアプローチ] -o（n^2）時間とo（1）スペース
- [より良いアプローチ] 2つのポインター技術を使用 - O（n log（n））時間とo（1）スペース
- [期待されるアプローチ]ハッシュセットを使用-O（n）時間とo（n）スペース
[ナイーブアプローチ]すべての可能なペアを生成することにより-O（n 2 ）時間とo（1）スペース
C++非常に基本的なアプローチは、可能なすべてのペアを生成し、製品が与えられたターゲット値に等しいペアが存在するかどうかを確認することです。 真実 。そのようなペアが存在しない場合は、戻ります 間違い 。
#include using namespace std ; // Function to check if any pair exists whose product // equals the target bool isProduct ( vector < int > & arr long long target ) { int n = arr . size (); for ( int i = 0 ; i < n - 1 ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { if ( 1L L * arr [ i ] * arr [ j ] == target ) { return true ; } } } return false ; } int main () { vector < int > arr = { 1 5 7 -1 5 }; long long target = 35 ; cout < < isProduct ( arr target ) < < endl ; return 0 ; }
C #include #include // Function to check if any pair exists whose product // equals the target bool isProduct ( int arr [] int n long long target ) { for ( int i = 0 ; i < n - 1 ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { if ( 1L L * arr [ i ] * arr [ j ] == target ) { return true ; } } } return false ; } int main () { int arr [] = { 1 5 7 -1 5 }; long long target = 35 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); printf ( '%d n ' isProduct ( arr n target )); return 0 ; }
Java class GfG { // Function to check if any pair exists whose product // equals the target static boolean isProduct ( int [] arr long target ) { int n = arr . length ; for ( int i = 0 ; i < n - 1 ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { if (( long ) arr [ i ] * arr [ j ] == target ) { return true ; } } } return false ; } public static void main ( String [] args ) { int [] arr = { 1 5 7 - 1 5 }; long target = 35 ; System . out . println ( isProduct ( arr target )); } }
Python # Function to check if any pair exists whose product # equals the target def is_product ( arr target ): n = len ( arr ) for i in range ( n - 1 ): for j in range ( i + 1 n ): if arr [ i ] * arr [ j ] == target : return True return False arr = [ 1 5 7 - 1 5 ] target = 35 print ( is_product ( arr target ))
C# using System ; class GfG { // Function to check if any pair exists whose product // equals the target static bool IsProduct ( int [] arr long target ) { int n = arr . Length ; for ( int i = 0 ; i < n - 1 ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { if (( long ) arr [ i ] * arr [ j ] == target ) { return true ; } } } return false ; } static void Main () { int [] arr = { 1 5 7 - 1 5 }; long target = 35 ; Console . WriteLine ( IsProduct ( arr target )); } }
JavaScript // Function to check if any pair exists whose product // equals the target function isProduct ( arr target ) { let n = arr . length ; for ( let i = 0 ; i < n - 1 ; i ++ ) { for ( let j = i + 1 ; j < n ; j ++ ) { if ( arr [ i ] * arr [ j ] === target ) { return true ; } } } return false ; } let arr = [ 1 5 7 - 1 5 ]; let target = 35 ; console . log ( isProduct ( arr target ));
出力
1
時間の複雑さ： 2つのネストされたループを使用するためのO（n²）
補助スペース： o（1）
[より良いアプローチ] 2つのポインター技術を使用 - O（n log（n））時間とo（1）スペース
C++この問題には2ポインター手法も使用できますが、ソートされたデータにのみ適用できます。したがって、最初に配列を並べ替えて、最初に2つのポインターを1つのポインターに保ちます（ 左 ）そして最後に（ 右 ）アレイの。次に、これら2つのポインターで要素の積を確認します。
- 製品が等しい場合 ターゲット ペアを見つけました。
- 製品がより少ない場合 ターゲット 移動します 左 へのポインタ 右 製品を増やすため。
- 製品がより大きい場合 ターゲット 移動します 右 へのポインタ 左 製品を減らすため。
#include using namespace std ; // Function to check if any pair exists whose product equals the target. bool isProduct ( vector < int > & arr long long target ) { // Sort the array sort ( arr . begin () arr . end ()); int left = 0 right = arr . size () - 1 ; while ( left < right ) { // Calculate the current product long long currProd = 1L L * arr [ left ] * arr [ right ]; // If the product matches the target return true. if ( currProd == target ) return true ; // Move the pointers based on comparison with target. if ( currProd > target ) right -- ; else left ++ ; } return false ; } int main () { vector < int > arr = { 1 5 7 -1 5 }; long long target = 35 ; cout < < isProduct ( arr target ) < < endl ; return 0 ; }
C #include #include #include // Function to compare two integers (used in qsort) int compare ( const void * a const void * b ) { return ( * ( int * ) a - * ( int * ) b ); } // Function to check if any pair exists whose product // equals the target. bool isProduct ( int arr [] int n long long target ) { // Sort the array qsort ( arr n sizeof ( int ) compare ); int left = 0 right = n - 1 ; while ( left < right ) { // Calculate the current product long long currProd = ( long long ) arr [ left ] * arr [ right ]; // If the product matches the target return true. if ( currProd == target ) return true ; // Move the pointers based on comparison with target. if ( currProd > target ) right -- ; else left ++ ; } return false ; } int main () { int arr [] = { 1 5 7 -1 5 }; long long target = 35 ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ]); printf ( '%d n ' isProduct ( arr n target )); return 0 ; }
Java import java.util.Arrays ; class GfG { // Function to check if any pair exists whose product equals the target. static boolean isProduct ( int [] arr long target ) { // Sort the array Arrays . sort ( arr ); int left = 0 right = arr . length - 1 ; while ( left < right ) { // Calculate the current product long currProd = ( long ) arr [ left ] * arr [ right ] ; // If the product matches the target return true. if ( currProd == target ) return true ; // Move the pointers based on comparison with target. if ( currProd > target ) right -- ; else left ++ ; } return false ; } public static void main ( String [] args ) { int [] arr = { 1 5 7 - 1 5 }; long target = 35 ; System . out . println ( isProduct ( arr target )); } }
Python # Function to check if any pair exists whose product equals the target. def isProduct ( arr target ): # Sort the array arr . sort () left right = 0 len ( arr ) - 1 while left < right : # Calculate the current product currProd = arr [ left ] * arr [ right ] # If the product matches the target return True. if currProd == target : return True # Move the pointers based on comparison with target. if currProd > target : right -= 1 else : left += 1 return False if __name__ == '__main__' : arr = [ 1 5 7 - 1 5 ] target = 35 print ( isProduct ( arr target ))
C# using System ; using System.Linq ; class GfG { // Function to check if any pair exists whose product // equals the target. static bool isProduct ( int [] arr long target ) { // Sort the array Array . Sort ( arr ); int left = 0 right = arr . Length - 1 ; while ( left < right ) { // Calculate the current product long currProd = ( long ) arr [ left ] * arr [ right ]; // If the product matches the target return true. if ( currProd == target ) return true ; // Move the pointers based on comparison with target. if ( currProd > target ) right -- ; else left ++ ; } return false ; } static void Main ( string [] args ) { int [] arr = { 1 5 7 - 1 5 }; long target = 35 ; Console . WriteLine ( isProduct ( arr target )); } }
JavaScript // Function to check if any pair exists whose product // equals the target. function isProduct ( arr target ) { // Sort the array arr . sort (( a b ) => a - b ); let left = 0 right = arr . length - 1 ; while ( left < right ) { // Calculate the current product let currProd = arr [ left ] * arr [ right ]; // If the product matches the target return true. if ( currProd === target ) return true ; // Move the pointers based on comparison with target. if ( currProd > target ) right -- ; else left ++ ; } return false ; } let arr = [ 1 5 7 - 1 5 ]; let target = 35 ; console . log ( isProduct ( arr target ));
出力
1
時間の複雑さ： o（n log（n））配列をソートするため
補助スペース： o（1）
[期待されるアプローチ]ハッシュセットを使用-O（n）時間とo（n）スペース
C++使用できます ハッシュセット 効率的に検索してください。配列を繰り返すと、各数値がターゲットの係数であるかどうかを確認します。もしそうなら、その対応する係数がすでにセットにあるかどうかを確認します。もしそうなら、私たちは戻ります 真実 ;それ以外の場合は、現在の番号をセットに追加して続行します。
#include #include #include using namespace std ; // Function to check if any pair exists whose product // equals the target. bool isProduct ( vector < int > & arr long long target ) { // Use an unordered set to store previously seen numbers. unordered_set < int > st ; for ( int num : arr ) { // If target is 0 and current number is 0 return true. if ( target == 0 && num == 0 ) return true ; // Check if current number can be a factor of the target. if ( target % num == 0 ) { int secondNum = target / num ; // If the secondNum has been seen before return true. if ( st . find ( secondNum ) != st . end ()) { return true ; } // Mark the current number as seen. st . insert ( num ); } } return false ; } int main () { vector < int > arr = { 1 5 7 -1 5 }; long long target = 35 ; cout < < isProduct ( arr target ) < < endl ; return 0 ; }
Java import java.util.HashSet ; class GfG { // Function to check if any pair exists whose product // equals the target. static boolean isProduct ( int [] arr long target ) { // Use a hash set to store previously seen numbers. HashSet < Integer > set = new HashSet <> (); for ( int num : arr ) { // If target is 0 and current number is 0 // return true. if ( target == 0 && num == 0 ) return true ; // Check if current number can be a factor of // the target. if ( target % num == 0 ) { int secondNum = ( int )( target / num ); // If the secondNum has been seen before // return true. if ( set . contains ( secondNum )) return true ; // Mark the current number as seen. set . add ( num ); } } return false ; } public static void main ( String [] args ) { int [] arr = { 1 5 7 - 1 5 }; long target = 35 ; System . out . println ( isProduct ( arr target )); } }
Python # Function to check if any pair exists whose product equals the target. def isProduct ( arr target ): # Use a set to store previously seen numbers. st = set () for num in arr : # If target is 0 and current number is 0 return True. if target == 0 and num == 0 : return True # Check if current number can be a factor of the target. if target % num == 0 : secondNum = target // num # If the secondNum has been seen before return True. if secondNum in st : return True # Mark the current number as seen. st . add ( num ) return False if __name__ == '__main__' : arr = [ 1 5 7 - 1 5 ] target = 35 print ( isProduct ( arr target ))
C# using System ; using System.Collections.Generic ; class GfG { // Function to check if any pair exists whose product // equals the target. static bool isProduct ( int [] arr long target ) { // Use a hash set to store previously seen numbers. HashSet < int > set = new HashSet < int > (); foreach ( int num in arr ) { // If target is 0 and current number is 0 // return true. if ( target == 0 && num == 0 ) return true ; // Check if current number can be a factor of // the target. if ( target % num == 0 ) { int secondNum = ( int )( target / num ); // If the secondNum has been seen before // return true. if ( set . Contains ( secondNum )) return true ; // Mark the current number as seen. set . Add ( num ); } } return false ; } static void Main ( string [] args ) { int [] arr = { 1 5 7 - 1 5 }; long target = 35 ; Console . WriteLine ( isProduct ( arr target )); } }
JavaScript // Function to check if any pair exists whose product equals // the target. function isProduct ( arr target ) { // Use a set to store previously seen numbers. let seen = new Set (); for ( let num of arr ) { // If target is 0 and current number is 0 return // true. if ( target === 0 && num === 0 ) return true ; // Check if current number can be a factor of the // target. if ( target % num === 0 ) { let secondNum = target / num ; // If the secondNum has been seen before return // true. if ( seen . has ( secondNum )) return true ; // Mark the current number as seen. seen . add ( num ); } } return false ; } let arr = [ 1 5 7 - 1 5 ]; let target = 35 ; console . log ( isProduct ( arr target ));
出力
1
時間の複雑さ： 単一の反復のO（n）
補助スペース： Hashセットに要素を保存するためのO（n）
