找到所有零和的三元组-yiteyi-C++库

给定一系列不同的元素。任务是在数组中找到和为零的三元组。

null

例如：

Input : arr[] = {0, -1, 2, -3, 1}Output : (0 -1 1), (2 -3 1)Explanation : The triplets with zero sum are0 + -1 + 1 = 0 and 2 + -3 + 1 = 0  Input : arr[] = {1, -2, 1, 0, 5}Output : 1 -2  1Explanation : The triplets with zero sum is1 + -2 + 1 = 0

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

方法1： 这是一个简单的方法，需要O（n ^3. )是时候得出结果了。

方法： naive方法运行三个循环，逐个检查三个元素的总和是否为零。如果三个元素之和为零，则打印元素，否则无法找到打印。
算法：
1. 使用循环计数器运行三个嵌套循环我 , J , K
2. 第一个循环从0到n-3，第二个循环从i+1到n-2，第三个循环从j+1到n-1。循环计数器代表三元组的三个元素。
3. 检查i’th，j’th，k’th的元素之和是否等于零。如果是，打印总数，否则继续。

以下是上述方法的实施情况：

C++

                         // A simple C++ program to find three elements                       
                         // whose sum is equal to zero                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Prints all triplets in arr[] with 0 sum                       
                         void                                     findTriplets(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 bool                                     found =                                     false                                     ;                       
                                                 for                                     (                                     int                                     i=0; i<n-2; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j=i+1; j<n-1; j++)                       
                                                 {                       
                                                 for                                     (                                     int                                     k=j+1; k<n; k++)                       
                                                 {                       
                                                 if                                     (arr[i]+arr[j]+arr[k] == 0)                       
                                                 {                       
                                                 cout << arr[i] <<                                     " "                       
                                                 << arr[j] <<                                     " "                       
                                                 << arr[k] <<endl;                       
                                                 found =                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // If no triplet with 0 sum found in array                       
                                                 if                                     (found ==                                     false                                     )                       
                                                 cout <<                                     " not exist "                                     <<endl;                       
           
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {0, -1, 2, -3, 1};                       
                                                 int                                     n =                                     sizeof                                     (arr)/                                     sizeof                                     (arr[0]);                       
                                                 findTriplets(arr, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // A simple Java program to find three elements                       
                         // whose sum is equal to zero                       
                         class                                     num{                       
                         // Prints all triplets in arr[] with 0 sum                       
                         static                                     void                                     findTriplets(                                     int                                     [] arr,                                     int                                     n)                       
                         {                       
                                                 boolean                                     found =                                     false                                     ;                       
                                                 for                                     (                                     int                                     i=                                     0                                     ; i<n-                                     2                                     ; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j=i+                                     1                                     ; j<n-                                     1                                     ; j++)                       
                                                 {                       
                                                 for                                     (                                     int                                     k=j+                                     1                                     ; k<n; k++)                       
                                                 {                       
                                                 if                                     (arr[i]+arr[j]+arr[k] ==                                     0                                     )                       
                                                 {                       
                                                 System.out.print(arr[i]);                       
                                                 System.out.print(                                     " "                                     );                       
                                                 System.out.print(arr[j]);                       
                                                 System.out.print(                                     " "                                     );                       
                                                 System.out.print(arr[k]);                       
                                                 System.out.print(                                     ""                                     );                       
                                                 found =                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // If no triplet with 0 sum found in array                       
                                                 if                                     (found ==                                     false                                     )                       
                                                 System.out.println(                                     " not exist "                                     );                       
           
                         }                       
           
                         // Driver code                       
                         public                                     static                                     void                                     main(String[] args)                       
                         {                       
                                                 int                                     arr[] = {                                     0                                     , -                                     1                                     ,                                     2                                     , -                                     3                                     ,                                     1                                     };                       
                                                 int                                     n =arr.length;                       
                                                 findTriplets(arr, n);                       
           
                         }                       
                         }                       
                         //This code is contributed by                       
                         //Smitha Dinesh Semwal                       

Python3

                         # A simple Python 3 program                       
                         # to find three elements whose                       
                         # sum is equal to zero                       
           
                         # Prints all triplets in                       
                         # arr[] with 0 sum                       
                         def                                     findTriplets(arr, n):                       
           
                                                 found                                     =                                     False                       
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n                                     -                                     2                                     ):                       
                                   
                                                 for                                     j                                     in                                     range                                     (i                                     +                                     1                                     , n                                     -                                     1                                     ):                       
                                   
                                                 for                                     k                                     in                                     range                                     (j                                     +                                     1                                     , n):                       
                                   
                                                 if                                     (arr[i]                                     +                                     arr[j]                                     +                                     arr[k]                                     =                                     =                                     0                                     ):                       
                                                 print                                     (arr[i], arr[j], arr[k])                       
                                                 found                                     =                                     True                       
                                   
                                   
                                                 # If no triplet with 0 sum                       
                                                 # found in array                       
                                                 if                                     (found                                     =                                     =                                     False                                     ):                       
                                                 print                                     (                                     " not exist "                                     )                       
           
                         # Driver code                       
                         arr                                     =                                     [                                     0                                     ,                                     -                                     1                                     ,                                     2                                     ,                                     -                                     3                                     ,                                     1                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         findTriplets(arr, n)                       
           
                         # This code is contributed by Smitha Dinesh Semwal                       

C#

                         // A simple C# program to find three elements                       
                         // whose sum is equal to zero                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 // Prints all triplets in arr[] with 0 sum                       
                                                 static                                     void                                     findTriplets(                                     int                                     []arr,                                     int                                     n)                       
                                                 {                       
                                                 bool                                     found =                                     false                                     ;                       
                                                 for                                     (                                     int                                     i = 0; i < n-2; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = i+1; j < n-1; j++)                       
                                                 {                       
                                                 for                                     (                                     int                                     k = j+1; k < n; k++)                       
                                                 {                       
                                                 if                                     (arr[i] + arr[j] + arr[k]                       
                                                 == 0)                       
                                                 {                       
                                                 Console.Write(arr[i]);                       
                                                 Console.Write(                                     " "                                     );                       
                                                 Console.Write(arr[j]);                       
                                                 Console.Write(                                     " "                                     );                       
                                                 Console.Write(arr[k]);                       
                                                 Console.Write(                                     ""                                     );                       
                                                 found =                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // If no triplet with 0 sum found in                       
                                                 // array                       
                                                 if                                     (found ==                                     false                                     )                       
                                                 Console.Write(                                     " not exist "                                     );                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     []arr = {0, -1, 2, -3, 1};                       
                                                 int                                     n = arr.Length;                       
                                                 findTriplets(arr, n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by nitin mittal.                       

PHP

                         <?php                       
                         // A simple PHP program to                       
                         // find three elements whose                       
                         // sum is equal to zero                       
           
                         // Prints all triplets                       
                         // in arr[] with 0 sum                       
                         function                                     findTriplets(                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                                 $found                                     = false;                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     - 2;                                     $i                                     ++)                       
                                                 {                       
                                                 for                                     (                                     $j                                     =                                     $i                                     + 1;                                     $j                                     <                                     $n                                     - 1;                                     $j                                     ++)                       
                                                 {                       
                                                 for                                     (                                     $k                                     =                                     $j                                     + 1;                                     $k                                     <                                     $n                                     ;                                     $k                                     ++)                       
                                                 {                       
                                                 if                                     (                                     $arr                                     [                                     $i                                     ] +                                     $arr                                     [                                     $j                                     ] +                       
                                                 $arr                                     [                                     $k                                     ] == 0)                       
                                                 {                       
                                                 echo                                     $arr                                     [                                     $i                                     ] ,                                     " "                                     ,                       
                                                 $arr                                     [                                     $j                                     ] ,                                     " "                                     ,                       
                                                 $arr                                     [                                     $k                                     ] ,                                     ""                                     ;                       
                                                 $found                                     = true;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // If no triplet with 0                       
                                                 // sum found in array                       
                                                 if                                     (                                     $found                                     == false)                       
                                                 echo                                     " not exist "                                     ,                                     ""                                     ;                       
           
                         }                       
           
                         // Driver Code                       
                         $arr                                     =                                     array                                     (0, -1, 2, -3, 1);                       
                         $n                                     = sizeof(                                     $arr                                     );                       
                         findTriplets(                                     $arr                                     ,                                     $n                                     );                       
           
                         // This code is contributed by m_kit                       
                         ?>                       

Javascript

                         <script>                       
                         // A simple Javascript program to find                       
                         //three elements whose sum is equal to zero                       
                                                 arr = [0, -1, 2, -3, 1];                       
                                   
                         // Prints all triplets in arr[] with 0 sum                       
                                                 function                                     findTriplets(arr) {                       
                                                 let found =                                     false                                     ;                       
                                                 for                                     (let i = 0; i < arr.length - 2; i++) {                       
                                                 for                                     (let j = i + 1; j < arr.length - 1; j++) {                       
                                                 for                                     (let k = j + 1; k < arr.length; k++) {                       
                                                 if                                     (arr[i] + arr[j] + arr[k] === 0)                       
                                                 {                       
                                                 document.write(arr[i]);                       
                                                 document.write(                                     " "                                     );                       
                                                 document.write(arr[j]);                       
                                                 document.write(                                     " "                                     );                       
                                                 document.write(arr[k]);                       
                                                 document.write(                                     "<br>"                                     );                       
                                                 found =                                     true                                     ;                       
                                   
                                                 }                       
                                                 }                       
                                                 }                       
                                                 // If no triplet with 0 sum found in array                       
                                                 if                                     (found ===                                     false                                     ) {                       
                                                 document.write(                                     " not exist "                                     );                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 findTriplets(arr);                       
                         // This code is contributed by Surbhi Tyagi                       
                         </script>                       

输出

0 -1 12 -3 1

复杂性分析：

时间复杂性： O（n） ^3. ). 由于需要三个嵌套循环，因此时间复杂度为O（n） ^3. ).
辅助空间： O（1）。因为不需要额外的空间，所以空间复杂度是恒定的。

方法2： 第二种方法使用散列过程来获得结果，并在较短的O（n）时间内求解 ^2. ).

方法： 这涉及遍历数组。对于每个元素arr[i]，找到一个和为“-arr[i]”的对。这个问题可以简化为对和，并且可以使用哈希在O（n）时间内解决。

算法：

创建一个hashmap来存储键值对。
运行一个包含两个循环的嵌套循环，外部循环从0到n-2，内部循环从i+1到n-1
检查哈希映射中是否存在第i个和第j个元素乘以-1的和
如果元素出现在hashmap中，则打印三元组，否则在hashmap中插入第j个元素。

以下是上述方法的实施情况：

C++

                         // C++ program to find triplets in a given                       
                         // array whose sum is zero                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to print triplets with 0 sum                       
                         void                                     findTriplets(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 bool                                     found =                                     false                                     ;                       
           
                                                 for                                     (                                     int                                     i=0; i<n-1; i++)                       
                                                 {                       
                                                 // Find all pairs with sum equals to                       
                                                 // "-arr[i]"                       
                                                 unordered_set<                                     int                                     > s;                       
                                                 for                                     (                                     int                                     j=i+1; j<n; j++)                       
                                                 {                       
                                                 int                                     x = -(arr[i] + arr[j]);                       
                                                 if                                     (s.find(x) != s.end())                       
                                                 {                       
                                                 printf                                     (                                     "%d %d %d"                                     , x, arr[i], arr[j]);                       
                                                 found =                                     true                                     ;                       
                                                 }                       
                                                 else                       
                                                 s.insert(arr[j]);                       
                                                 }                       
                                                 }                       
           
                                                 if                                     (found ==                                     false                                     )                       
                                                 cout <<                                     " No Triplet Found"                                     << endl;                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {0, -1, 2, -3, 1};                       
                                                 int                                     n =                                     sizeof                                     (arr)/                                     sizeof                                     (arr[0]);                       
                                                 findTriplets(arr, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find triplets in a given                       
                         // array whose sum is zero                       
                         import                                     java.util.*;                       
           
                         class                                     GFG                       
                         {                       
           
                                                 // function to print triplets with 0 sum                       
                                                 static                                     void                                     findTriplets(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 boolean                                     found =                                     false                                     ;                       
           
                                                 for                                     (                                     int                                     i =                                     0                                     ; i < n -                                     1                                     ; i++)                       
                                                 {                       
                                                 // Find all pairs with sum equals to                       
                                                 // "-arr[i]"                       
                                                 HashSet<Integer> s =                                     new                                     HashSet<Integer>();                       
                                                 for                                     (                                     int                                     j = i +                                     1                                     ; j < n; j++)                       
                                                 {                       
                                                 int                                     x = -(arr[i] + arr[j]);                       
                                                 if                                     (s.contains(x))                       
                                                 {                       
                                                 System.out.printf(                                     "%d %d %d"                                     , x, arr[i], arr[j]);                       
                                                 found =                                     true                                     ;                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 s.add(arr[j]);                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 if                                     (found ==                                     false                                     )                       
                                                 {                       
                                                 System.out.printf(                                     " No Triplet Found"                                     );                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     0                                     , -                                     1                                     ,                                     2                                     , -                                     3                                     ,                                     1                                     };                       
                                                 int                                     n = arr.length;                       
                                                 findTriplets(arr, n);                       
                                                 }                       
                         }                       
           
                         // This code contributed by Rajput-Ji                       

Python3

                         # Python3 program to find triplets                       
                         # in a given array whose sum is zero                       
           
                         # function to print triplets with 0 sum                       
                         def                                     findTriplets(arr, n):                       
                                                 found                                     =                                     False                       
                                                 for                                     i                                     in                                     range                                     (n                                     -                                     1                                     ):                       
           
                                                 # Find all pairs with sum                       
                                                 # equals to "-arr[i]"                       
                                                 s                                     =                                     set                                     ()                       
                                                 for                                     j                                     in                                     range                                     (i                                     +                                     1                                     , n):                       
                                                 x                                     =                                     -                                     (arr[i]                                     +                                     arr[j])                       
                                                 if                                     x                                     in                                     s:                       
                                                 print                                     (x, arr[i], arr[j])                       
                                                 found                                     =                                     True                       
                                                 else                                     :                       
                                                 s.add(arr[j])                       
                                                 if                                     found                                     =                                     =                                     False                                     :                       
                                                 print                                     (                                     "No Triplet Found"                                     )                       
           
                         # Driver Code                       
                         arr                                     =                                     [                                     0                                     ,                                     -                                     1                                     ,                                     2                                     ,                                     -                                     3                                     ,                                     1                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         findTriplets(arr, n)                       
           
                         # This code is contributed by Shrikant13                       

C#

                         // C# program to find triplets in a given                       
                         // array whose sum is zero                       
                         using                                     System;                       
                         using                                     System.Collections.Generic;                       
           
                         class                                     GFG                       
                         {                       
           
                                                 // function to print triplets with 0 sum                       
                                                 static                                     void                                     findTriplets(                                     int                                     []arr,                                     int                                     n)                       
                                                 {                       
                                                 bool                                     found =                                     false                                     ;                       
           
                                                 for                                     (                                     int                                     i = 0; i < n - 1; i++)                       
                                                 {                       
                                                 // Find all pairs with sum equals to                       
                                                 // "-arr[i]"                       
                                                 HashSet<                                     int                                     > s =                                     new                                     HashSet<                                     int                                     >();                       
                                                 for                                     (                                     int                                     j = i + 1; j < n; j++)                       
                                                 {                       
                                                 int                                     x = -(arr[i] + arr[j]);                       
                                                 if                                     (s.Contains(x))                       
                                                 {                       
                                                 Console.Write(                                     "{0} {1} {2}"                                     , x, arr[i], arr[j]);                       
                                                 found =                                     true                                     ;                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 s.Add(arr[j]);                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 if                                     (found ==                                     false                                     )                       
                                                 {                       
                                                 Console.Write(                                     " No Triplet Found"                                     );                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 int                                     []arr = {0, -1, 2, -3, 1};                       
                                                 int                                     n = arr.Length;                       
                                                 findTriplets(arr, n);                       
                                                 }                       
                         }                       
           
                         // This code has been contributed by 29AjayKumar                       

Javascript

                         <script>                       
                                   
                         // Javascript program to find triplets in a given                       
                         // array whose sum is zero                       
           
                         // function to print triplets with 0 sum                       
                         function                                     findTriplets(arr, n)                       
                         {                       
                                                 var                                     found =                                     false                                     ;                       
           
                                                 for                                     (                                     var                                     i = 0; i < n - 1; i++)                       
                                                 {                       
                                                 // Find all pairs with sum equals to                       
                                                 // "-arr[i]"                       
                                                 var                                     s =                                     new                                     Set();                       
                                                 for                                     (                                     var                                     j = i + 1; j < n; j++)                       
                                                 {                       
                                                 var                                     x = -(arr[i] + arr[j]);                       
                                                 if                                     (s.has(x))                       
                                                 {                       
                                                 document.write( x +                                     " "                                     + arr[i] +                                     " "                                     + arr[j] +                                     "<br>"                                     );                       
                                                 found =                                     true                                     ;                       
                                                 }                       
                                                 else                       
                                                 s.add(arr[j]);                       
                                                 }                       
                                                 }                       
           
                                                 if                                     (found ==                                     false                                     )                       
                                                 document.write(                                     " No Triplet Found"                                     );                       
                         }                       
           
                         // Driver code                       
                         var                                     arr = [0, -1, 2, -3, 1];                       
                         var                                     n = arr.length;                       
                         findTriplets(arr, n);                       
           
                         // This code is contributed by famously.                       
                         </script>                       

输出

-1 0 1-3 2 1

复杂性分析：

时间复杂性： O（n） ^2. ). 由于需要两个嵌套循环，因此时间复杂度为O（n） ^2. ).
辅助空间： O（n）。因为需要hashmap，所以空间复杂度是线性的。

方法3： 该方法使用排序来获得正确的结果，并在O（n）中求解 ^2. )时间到了。

方法： 上述方法需要额外的空间。这个想法是基于这邮递对于每个元素，检查是否有一对元素的和等于该元素的负值。

算法：

按升序对数组排序。
从头到尾遍历阵列。
对于每个索引我，创建两个变量 l=i+1 和 r=n-1
如果数组[i]、数组[l]和数组[r]之和等于零，则运行循环直到l小于r，然后打印三元组并断开循环
如果总和小于零，则增加l的值，通过增加l的值，总和将随着数组的排序而增加，因此 数组[l+1]>数组[l]
如果总和大于零，则减小r的值，通过减小r的值，总和将随着数组的排序而减小，因此 数组[r-1] .

以下是上述方法的实施情况：

C++

                         // C++ program to find triplets in a given                       
                         // array whose sum is zero                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // function to print triplets with 0 sum                       
                         void                                     findTriplets(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 bool                                     found =                                     false                                     ;                       
           
                                                 // sort array elements                       
                                                 sort(arr, arr+n);                       
           
                                                 for                                     (                                     int                                     i=0; i<n-1; i++)                       
                                                 {                       
                                                 // initialize left and right                       
                                                 int                                     l = i + 1;                       
                                                 int                                     r = n - 1;                       
                                                 int                                     x = arr[i];                       
                                                 while                                     (l < r)                       
                                                 {                       
                                                 if                                     (x + arr[l] + arr[r] == 0)                       
                                                 {                       
                                                 // print elements if it's sum is zero                       
                                                 printf                                     (                                     "%d %d %d"                                     , x, arr[l], arr[r]);                       
                                                 l++;                       
                                                 r--;                       
                                                 // found = true;                       
                                                 //   break;                       
                                                 }                       
           
                                                 // If sum of three elements is less                       
                                                 // than zero then increment in left                       
                                                 else                                     if                                     (x + arr[l] + arr[r] < 0)                       
                                                 l++;                       
           
                                                 // if sum is greater than zero than                       
                                                 // decrement in right side                       
                                                 else                       
                                                 r--;                       
                                                 }                       
                                                 }                       
           
                                                 if                                     (found ==                                     false                                     )                       
                                                 cout <<                                     " No Triplet Found"                                     << endl;                       
                         }                       
           
                         // Driven source                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {0, -1, 2, -3, 1};                       
                                                 int                                     n =                                     sizeof                                     (arr)/                                     sizeof                                     (arr[0]);                       
                                                 findTriplets(arr, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java  program to find triplets in a given                       
                         // array whose sum is zero                       
                         import                                     java.util.Arrays;                       
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
                                                 // function to print triplets with 0 sum                       
                         static                                     void                                     findTriplets(                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 boolean                                     found =                                     false                                     ;                       
           
                                                 // sort array elements                       
                                                 Arrays.sort(arr);                       
           
                                                 for                                     (                                     int                                     i=                                     0                                     ; i<n-                                     1                                     ; i++)                       
                                                 {                       
                                                 // initialize left and right                       
                                                 int                                     l = i +                                     1                                     ;                       
                                                 int                                     r = n -                                     1                                     ;                       
                                                 int                                     x = arr[i];                       
                                                 while                                     (l < r)                       
                                                 {                       
                                                 if                                     (x + arr[l] + arr[r] ==                                     0                                     )                       
                                                 {                       
                                                 // print elements if it's sum is zero                       
                                                 System.out.print(x +                                     " "                                     );                       
                                                 System.out.print(arr[l]+                                     " "                                     );                       
                                                 System.out.println(arr[r]+                                     " "                                     );                       
                                   
                                                 l++;                       
                                                 r--;                       
                                                 found =                                     true                                     ;                       
                                                 }                       
           
                                                 // If sum of three elements is less                       
                                                 // than zero then increment in left                       
                                                 else                                     if                                     (x + arr[l] + arr[r] <                                     0                                     )                       
                                                 l++;                       
           
                                                 // if sum is greater than zero than                       
                                                 // decrement in right side                       
                                                 else                       
                                                 r--;                       
                                                 }                       
                                                 }                       
           
                                                 if                                     (found ==                                     false                                     )                       
                                                 System.out.println(                                     " No Triplet Found"                                     );                       
                         }                       
           
                         // Driven source                       
                                                 public                                     static                                     void                                     main (String[] args) {                       
           
                                                 int                                     arr[] = {                                     0                                     , -                                     1                                     ,                                     2                                     , -                                     3                                     ,                                     1                                     };                       
                                                 int                                     n =arr.length;                       
                                                 findTriplets(arr, n);                       
                                                 }                       
                         //This code is contributed by Tushil..                       
                         }                       

Python3

                         # python program to find triplets in a given                       
                         # array whose sum is zero                       
           
                         # function to print triplets with 0 sum                       
                         def                                     findTriplets(arr, n):                       
           
                                                 found                                     =                                     False                       
           
                                                 # sort array elements                       
                                                 arr.sort()                       
           
                                                 for                                     i                                     in                                     range                                     (                                     0                                     , n                                     -                                     1                                     ):                       
                                   
                                                 # initialize left and right                       
                                                 l                                     =                                     i                                     +                                     1                       
                                                 r                                     =                                     n                                     -                                     1                       
                                                 x                                     =                                     arr[i]                       
                                                 while                                     (l < r):                       
                                   
                                                 if                                     (x                                     +                                     arr[l]                                     +                                     arr[r]                                     =                                     =                                     0                                     ):                       
                                                 # print elements if it's sum is zero                       
                                                 print                                     (x, arr[l], arr[r])                       
                                                 l                                     +                                     =                                     1                       
                                                 r                                     -                                     =                                     1                       
                                                 found                                     =                                     True                       
                                   
           
                                                 # If sum of three elements is less                       
                                                 # than zero then increment in left                       
                                                 elif                                     (x                                     +                                     arr[l]                                     +                                     arr[r] <                                     0                                     ):                       
                                                 l                                     +                                     =                                     1                       
           
                                                 # if sum is greater than zero than                       
                                                 # decrement in right side                       
                                                 else                                     :                       
                                                 r                                     -                                     =                                     1                       
                                   
                                                 if                                     (found                                     =                                     =                                     False                                     ):                       
                                                 print                                     (                                     " No Triplet Found"                                     )                       
           
           
                         # Driven source                       
                         arr                                     =                                     [                                     0                                     ,                                     -                                     1                                     ,                                     2                                     ,                                     -                                     3                                     ,                                     1                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         findTriplets(arr, n)                       
           
                         # This code is contributed by Smitha Dinesh Semwal                       

C#

                         // C#  program to find triplets in a given                       
                         // array whose sum is zero                       
                         using                                     System;                       
           
                         public                                     class                                     GFG{                       
                                                 // function to print triplets with 0 sum                       
                         static                                     void                                     findTriplets(                                     int                                     []arr,                                     int                                     n)                       
                         {                       
                                                 bool                                     found =                                     false                                     ;                       
           
                                                 // sort array elements                       
                                                 Array.Sort(arr);                       
           
                                                 for                                     (                                     int                                     i=0; i<n-1; i++)                       
                                                 {                       
                                                 // initialize left and right                       
                                                 int                                     l = i + 1;                       
                                                 int                                     r = n - 1;                       
                                                 int                                     x = arr[i];                       
                                                 while                                     (l < r)                       
                                                 {                       
                                                 if                                     (x + arr[l] + arr[r] == 0)                       
                                                 {                       
                                                 // print elements if it's sum is zero                       
                                                 Console.Write(x +                                     " "                                     );                       
                                                 Console.Write(arr[l]+                                     " "                                     );                       
                                                 Console.WriteLine(arr[r]+                                     " "                                     );                       
                                   
                                                 l++;                       
                                                 r--;                       
                                                 found =                                     true                                     ;                       
                                                 }                       
           
                                                 // If sum of three elements is less                       
                                                 // than zero then increment in left                       
                                                 else                                     if                                     (x + arr[l] + arr[r] < 0)                       
                                                 l++;                       
           
                                                 // if sum is greater than zero than                       
                                                 // decrement in right side                       
                                                 else                       
                                                 r--;                       
                                                 }                       
                                                 }                       
           
                                                 if                                     (found ==                                     false                                     )                       
                                                 Console.WriteLine(                                     " No Triplet Found"                                     );                       
                         }                       
           
                         // Driven source                       
                                                 static                                     public                                     void                                     Main (){                       
                                   
                                                 int                                     []arr = {0, -1, 2, -3, 1};                       
                                                 int                                     n =arr.Length;                       
                                                 findTriplets(arr, n);                       
                                                 }                       
                         //This code is contributed by akt_mit..                       
                         }                       

PHP

                         <?php                       
                         // PHP program to find                       
                         // triplets in a given                       
                         // array whose sum is zero                       
           
                         // function to print                       
                         // triplets with 0 sum                       
                         function                                     findTriplets(                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                                 $found                                     = false;                       
           
                                                 // sort array elements                       
                                                 sort(                                     $arr                                     );                       
           
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     - 1;                                     $i                                     ++)                       
                                                 {                       
                                                 // initialize left                       
                                                 // and right                       
                                                 $l                                     =                                     $i                                     + 1;                       
                                                 $r                                     =                                     $n                                     - 1;                       
                                                 $x                                     =                                     $arr                                     [                                     $i                                     ];                       
                                                 while                                     (                                     $l                                     <                                     $r                                     )                       
                                                 {                       
                                                 if                                     (                                     $x                                     +                                     $arr                                     [                                     $l                                     ] +                       
                                                 $arr                                     [                                     $r                                     ] == 0)                       
                                                 {                       
                                                 // print elements if                       
                                                 // it's sum is zero                       
                                                 echo                                     $x                                     ,                                     " "                                     ,                                     $arr                                     [                                     $l                                     ],                       
                                                 " "                                     ,                                     $arr                                     [                                     $r                                     ],                                     ""                                     ;                       
                                                 $l                                     ++;                       
                                                 $r                                     --;                       
                                                 $found                                     = true;                       
                                                 }                       
           
                                                 // If sum of three elements                       
                                                 // is less than zero then                       
                                                 // increment in left                       
                                                 else                                     if                                     (                                     $x                                     +                                     $arr                                     [                                     $l                                     ] +                       
                                                 $arr                                     [                                     $r                                     ] < 0)                       
                                                 $l                                     ++;                       
           
                                                 // if sum is greater than                       
                                                 // zero than decrement                       
                                                 // in right side                       
                                                 else                       
                                                 $r                                     --;                       
                                                 }                       
                                                 }                       
           
                                                 if                                     (                                     $found                                     == false)                       
                                                 echo                                     " No Triplet Found"                                     ,                                     ""                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $arr                                     =                                     array                                     (0, -1, 2, -3, 1);                       
                         $n                                     = sizeof(                                     $arr                                     );                       
                         findTriplets(                                     $arr                                     ,                                     $n                                     );                       
           
                         // This code is contributed by ajit                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to find triplets in a given                       
                         // array whose sum is zero                       
           
                         // function to print triplets with 0 sum                       
                         function                                     findTriplets(arr, n)                       
                         {                       
                                                 let found =                                     false                                     ;                       
           
                                                 // sort array elements                       
                                                 arr.sort((a, b) => a - b);                       
           
                                                 for                                     (let i=0; i<n-1; i++)                       
                                                 {                       
                                                 // initialize left and right                       
                                                 let l = i + 1;                       
                                                 let r = n - 1;                       
                                                 let x = arr[i];                       
                                                 while                                     (l < r)                       
                                                 {                       
                                                 if                                     (x + arr[l] + arr[r] == 0)                       
                                                 {                       
                                                 // print elements if it's sum is zero                       
                                                 document.write(x +                                     " "                                     );                       
                                                 document.write(arr[l]+                                     " "                                     );                       
                                                 document.write(arr[r]+                                     " "                                     +                                     "<br>"                                     );                       
                                                 l++;                       
                                                 r--;                       
                                                 found =                                     true                                     ;                       
                                                 }                       
           
                                                 // If sum of three elements is less                       
                                                 // than zero then increment in left                       
                                                 else                                     if                                     (x + arr[l] + arr[r] < 0)                       
                                                 l++;                       
           
                                                 // if sum is greater than zero than                       
                                                 // decrement in right side                       
                                                 else                       
                                                 r--;                       
                                                 }                       
                                                 }                       
           
                                                 if                                     (found ==                                     false                                     )                       
                                                 document.write(                                     " No Triplet Found"                                     +                                     "<br>"                                     );                       
                         }                       
           
                         // Driven source                       
           
                                                 let arr = [0, -1, 2, -3, 1];                       
                                                 let n = arr.length;                       
                                                 findTriplets(arr, n);                       
           
           
                         // This code is contributed by Mayank Tyagi                       
           
                         </script>                       

输出

-3 1 2-1 0 1

复杂性分析：

时间复杂性： O（n） ^2. ). 只需要两个嵌套循环，因此时间复杂度为O（n） ^2. ).
辅助空间： O（1），不需要额外的空间，因此时间复杂度是恒定的。

本文由 丹麦拉扎 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章