用给定的和打印所有三元组-yiteyi-C++库

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

null

例如：

Input: arr[] = {0, -1, 2, -3, 1}        sum = -2Output:  0 -3  1        -1  2 -3If we calculate the sum of the output,0 + (-3) + 1 = -2(-1) + 2 + (-3) = -2Input: arr[] = {1, -2, 1, 0, 5}       sum = 0Output: 1 -2  1If we calculate the sum of the output,1 + (-2) + 1 = 0

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

方法1 : 蛮力。 方法： 这类问题中的蛮力方法旨在检查数组中所有可能的三胞胎。三胞胎 总和=目标总和 这就是答案。现在出现的问题是如何检查所有可能的三胞胎。检查所有可能的小品在一个元素上固定一个指针，对于每个这样的元素，遍历数组并检查总和。这将是所有可能的总和小品 .

同样用于检查所有可能的 三胞胎 可以固定两个指针并将第三个指针移动到数组上，当它到达数组末尾时，增加第二个指针，然后再次重复相同的操作。

算法：

拿三分球我 , J , K .
初始化我使用零并开始一个嵌套循环我 .
初始化 J 具有 （i+1） 然后开始一个嵌套循环 J .
初始化 K 具有 （j+1） 然后开始一个循环 K .
如果 目标==arr[i]+arr[j]+arr[k] 打破循环并打印 arr[i]，arr[j]，arr[k] .
否则就继续增加 K 直到它等于 最后索引 .
转到第二步 和增量 J 对于每一个价值 J 运行 K .
如果 J 等于 倒数第二 转到第一步 并增加我直到 最后三个索引 然后继续整个过程直到我等于最后一个索引。

C++

                         // A simple C++ program to find three elements                       
                         // whose sum is equal to given sum                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Prints all triplets in arr[] with given sum                       
                         void                                     findTriplets(                                     int                                     arr[],                                     int                                     n,                                     int                                     sum)                       
                         {                       
                                                 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] == sum) {                       
                                                 cout << arr[i] <<                                     " "                       
                                                 << arr[j] <<                                     " "                       
                                                 << arr[k] << endl;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 0, -1, 2, -3, 1 };                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 findTriplets(arr, n, -2);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // A simple Java program                       
                         // to find three elements                       
                         // whose sum is equal to                       
                         // given sum                       
                         import                                     java.io.*;                       
           
                         class                                     GFG {                       
           
                                                 // Prints all triplets in                       
                                                 // arr[] with given sum                       
                                                 static                                     void                                     findTriplets(                                     int                                     arr[],                       
                                                 int                                     n,                                     int                                     sum)                       
                                                 {                       
                                                 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] == sum) {                       
                                                 System.out.println(                       
                                                 arr[i] +                                     " "                                     + arr[j]                       
                                                 +                                     " "                                     + arr[k]);                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     arr[] = {                                     0                                     , -                                     1                                     ,                                     2                                     , -                                     3                                     ,                                     1                                     };                       
                                                 int                                     n = arr.length;                       
                                                 findTriplets(arr, n, -                                     2                                     );                       
                                                 }                       
                         }                       
           
                         // This code is contributed by m_kit                       

Python3

                         # A simple Python 3 program                       
                         # to find three elements                       
                         # whose sum is equal to                       
                         # given sum                       
           
                         # Prints all triplets in                       
                         # arr[] with given sum                       
                         def                                     findTriplets(arr, n,                                     sum                                     ):                       
           
                                                 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]                                     =                                     =                                     sum                                     ):                       
                                                 print                                     (arr[i],                                     " "                                     ,                       
                                                 arr[j],                                     " "                                     ,                       
                                                 arr[k], sep                                     =                                     "")                       
                                   
                         # Driver code                       
                         arr                                     =                                     [                                     0                                     ,                                     -                                     1                                     ,                                     2                                     ,                                     -                                     3                                     ,                                     1                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         findTriplets(arr, n,                                     -                                     2                                     )                       
           
                         # This code is contributed                       
                         # by Smitha                       

C#

                         // A simple C# program                       
                         // to find three elements                       
                         // whose sum is equal to                       
                         // given sum                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 // Prints all triplets in                       
                                                 // arr[] with given sum                       
                                                 static                                     void                                     findTriplets(                                     int                                     [] arr,                       
                                                 int                                     n,                                     int                                     sum)                       
                                                 {                       
                                                 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] == sum) {                       
                                                 Console.WriteLine(                       
                                                 arr[i] +                                     " "                                     + arr[j]                       
                                                 +                                     " "                                     + arr[k]);                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                                 static                                     public                                     void                                     Main()                       
                                                 {                       
                                                 int                                     [] arr = { 0, -1, 2, -3, 1 };                       
                                                 int                                     n = arr.Length;                       
                                                 findTriplets(arr, n, -2);                       
                                                 }                       
                         }                       
                         // This code is contributed by akt_mit                       

PHP

                         <?php                       
                         // A simple PHP program to                       
                         // find three elements whose                       
                         // sum is equal to given sum                       
           
                         // Prints all triplets in                       
                         // arr[] with given sum                       
                         function                                     findTriplets(                                     $arr                                     ,                                     $n                                     ,                                     $sum                                     )                       
                         {                       
                                                 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                                     ] ==                                     $sum                                     )                       
                                                 {                       
                                                 echo                                     $arr                                     [                                     $i                                     ],                                     " "                                     ,                       
                                                 $arr                                     [                                     $j                                     ],                                     " "                                     ,                       
                                                 $arr                                     [                                     $k                                     ],                                     ""                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         $arr                                     =                                     array                                     (0, -1, 2, -3, 1);                       
                         $n                                     = sizeof(                                     $arr                                     );                       
                         findTriplets(                                     $arr                                     ,                                     $n                                     , -2);                       
           
                         // This code is contributed by aj_36                       
                         ?>                       

Javascript

                         <script>                       
           
                         // A simple Javascript program to find three elements                       
                         // whose sum is equal to given sum                       
           
                         // Prints all triplets in arr[] with given sum                       
                         function                                     findTriplets(arr, n, sum)                       
                         {                       
                                                 for                                     (let i = 0; i < n - 2; i++) {                       
                                                 for                                     (let j = i + 1; j < n - 1; j++) {                       
                                                 for                                     (let k = j + 1; k < n; k++) {                       
                                                 if                                     (arr[i] + arr[j] + arr[k] == sum) {                       
                                                 document.write(arr[i]+                                     " "                       
                                                 + arr[j] +                                     " "                       
                                                 + arr[k] +                                     "<br>"                                     );                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver code                       
           
                                                 let arr = [ 0, -1, 2, -3, 1 ];                       
                                                 let n = arr.length;                       
                                                 findTriplets(arr, n, -2);                       
           
                         // This code is contributed by Mayank Tyagi                       
           
                         </script>                       

输出：

0 -3 1-1 2 -3

复杂性分析：

时间复杂性： O（n） ^3. ). 因为使用了三个嵌套for循环。
辅助空间： O（1）。因为没有使用数据结构来存储值。

方法2 : 散列。

方法： 哈希可以用来解决这个问题。HashTable或HashMaps允许我们以恒定的时间复杂度执行查找或搜索操作。如果你能发现每一个可能的duplet都有一个元素存在于数组中 总和=目标总和 然后这个问题就会得到有效的解决。要实现哈希，我们可以使用 C++中的无序序集或 Java中的哈希集 .

当我们修正第一个指针时 （说a） ，使用第二个指针遍历数组 （说b） 并继续存储 散列表 .
一旦我们发现元素等于剩余和 （目标金额-（a+b）） 这已经存在于 散列表 ，我们打印三胞胎。

算法：

从外部循环开始 i=0 直到 （n-2）第 指数
对于每一次迭代，创建一个无序集并进入内部循环。
启动内部循环[从 j=（i+1） （因为我们已经检查过的值不会出现在有效的三元组中）直到 最后一个索引。
检查元素是否正确 x=目标-（arr[i]+arr[j]） 然后找到三胞胎并打印出来。
否则，按下集合中的值，以供以后参考。
定期的加薪我然后进入第二步。

伪代码：

Run a loop from i=0 to n-2  Create an empty hash table  Run inner loop from j=i+1 to n-1      If -(arr[i] + arr[j]) is present in hash table         print arr[i], arr[j] and -(arr[i] + arr[j])      Else         Insert arr[j] in hash table.

C++

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

JAVA

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

Python3

                         # Python3 program to find triplets in a given                       
                         # array whose Sum is equal to given sum.                       
                         import                                     math as mt                       
           
                         # function to print triplets with given sum                       
                         def                                     findTriplets(arr, n,                                     Sum                                     ):                       
           
                                                 for                                     i                                     in                                     range                                     (n                                     -                                     1                                     ):                       
                                   
                                                 # Find all pairs with Sum equals                       
                                                 # to "Sum-arr[i]"                       
                                                 s                                     =                                     dict                                     ()                       
                                                 for                                     j                                     in                                     range                                     (i                                     +                                     1                                     , n):                       
                                                 x                                     =                                     Sum                                     -                                     (arr[i]                                     +                                     arr[j])                       
                                                 if                                     x                                     in                                     s.keys():                       
                                                 print                                     (x, arr[i], arr[j])                       
                                                 else                                     :                       
                                                 s[arr[j]]                                     =                                     1                       
                                   
                         # Driver code                       
                         arr                                     =                                     [                                     0                                     ,                                     -                                     1                                     ,                                     2                                     ,                                     -                                     3                                     ,                                     1                                     ]                       
                         Sum                                     =                                     -                                     2                       
                         n                                     =                                     len                                     (arr)                       
                         findTriplets(arr, n,                                     Sum                                     )                       
           
                         # This code is contributed                       
                         # by mohit kumar 29                       

C#

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

Javascript

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

输出：

-3 0 12 -1 -3

复杂性分析：

时间复杂性： O（n） ^2. ). 使用嵌套for循环将时间复杂度提高到n ^2. .
辅助空间： O（n）。作为一种无序的集合，数据结构被用于存储值。

方法3 : 该方法采用排序法和双指针技术来解决上述问题。这次执行将涉及O（n ^2. ))时间复杂度和O（1）空间复杂度。这个想法是基于这邮递

方法： 这个 双指针技术 可以使用排序技术将其付诸实施。在双指针技术中，一个人可以搜索具有目标和的对 线性时间 .这里的想法是修复一个指针 （说a） 并使用剩余的指针找到具有所需和的对 目标值（a） 效率很高。现在，让我们讨论如何使用双指针技术有效地找到所需的对。用于双指针技术的指针是 （左和右） .

所以如果 总和=值（a）+值（l）+值（r） 超过所需金额，相同 （a，l） 必要的 价值（r） 应该比以前少。因此，减少 R 指针。
如果 总和=值（a）+值（l）+值（r） 小于所需金额，相同 （a，r） 必要的 价值（l） 应大于上一个。因此，增加 L 指针。

算法：

对数组和每个元素进行排序 arr[i] 搜索其他两个元素 arr[l]，arr[r] 以至于 arr[i]+arr[l]+arr[r]=目标和 .
搜索其他两个元素可以使用 双指针技术 当数组被排序时。
运行一个外部循环，将控制变量作为我对于每次迭代，初始化一个值 L 哪一个是第一个指针 i+1 和 R 最后一个索引。
现在进入while循环，直到 l .
如果 arr[i]+arr[l]+arr[r]>目标和 然后减量 R 通过 1. 由于所需的总和小于当前总和，因此降低的值将起到必要的作用。
如果 arr[i]+arr[l]+arr[r] 然后增加 L 通过 1. 由于所需的总和小于当前总和，增加的值将达到所需的效果。
如果 arr[i]+arr[l]+arr[r]==目标和 打印值。
定期的加薪我转到第三步。

伪代码：

1. Sort all element of array2. Run loop from i=0 to n-2.     Initialize two index variables l=i+1 and r=n-14. while (l < r)      Check sum of arr[i], arr[l], arr[r] is     given sum or not if sum is 'sum', then print      the triplet and do l++ and r--.5. If sum is less than given sum then l++6. If sum is greater than given sum then r--7. If not exist in array then print not found.

C++

                         // C++ program to find triplets in a given                       
                         // array whose sum is given sum.                       
                         #include <bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Function to print triplets with given sum                       
                                                 vector<vector<                                     int                                     >> findTriplets(                                     int                                     nums[],                                     int                                     n,                                     int                                     sumTarget) {                       
                                                 vector<vector<                                     int                                     >> res;                       
                                                 if                                     (n <=2)                                     return                                     res;                       
                                   
                                                 sort(nums,nums + n);                       
                                   
                                                 for                                     (                                     int                                     i=0;i<n;i++){                       
                                   
                                                 if                                     (i>0 && nums[i] == nums[i-1])                                     // avoid duplicate triplets count                       
                                                 continue                                     ;                       
                                   
                                                 int                                     num = nums[i];                       
                                                 int                                     target = sumTarget - num;                       
                                   
                                                 for                                     (                                     int                                     l=i+1, r=n-1; l<r; ) {                       
                                   
                                                 if                                     (nums[l]+nums[r] > target)                       
                                                 r--;                       
                                   
                                                 else                                     if                                     (nums[l]+nums[r] < target)                       
                                                 l++;                       
                                   
                                                 else                                     {                       
                                                 // nums[l] + nums[r] == target                       
                                                 res.push_back({nums[i], nums[l], nums[r]});                       
           
                                                 // skip duplicates                       
                                                 while                                     ( l<n-1 && nums[l]==nums[l+1]) l++;                       
                                                 while                                     ( r>0 && nums[r]==nums[r-1]) r--;                       
                                   
                                                 l++;                       
                                                 r--;                       
                                   
                                                 }                       
                                   
                                                 }                       
                                   
                                                 }                       
                                                 return                                     res;                       
                                                 }                       
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = { 0, -1, 2, -3, 1, -1, 3, 0};                       
                                                 int                                     sum = -2;                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 vector<vector<                                     int                                     >> res = findTriplets(arr, n, sum);                       
                                                 cout<<                                     "Unique triplets found are : "                                     ;                       
                                                 for                                     (                                     int                                     i = 0;i<res.size();i++)                       
                                                 cout<<res[i][0]<<                                     " "                                     <<res[i][1]<<                                     " "                                     <<res[i][2]<<                                     ""                                     ;                       
                                   
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find triplets                       
                         // in a given array whose sum                       
                         // is given sum.                       
                         import                                     java.io.*;                       
                         import                                     java.util.*;                       
           
                         class                                     GFG {                       
           
                                                 // function to print                       
                                                 // triplets with given sum                       
                                                 static                                     void                                     findTriplets(                                     int                                     [] arr,                       
                                                 int                                     n,                                     int                                     sum)                       
                                                 {                       
                                                 // 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] == sum) {                       
                                                 // print elements if it's                       
                                                 // sum is given sum.                       
                                                 System.out.println(                       
                                                 x +                                     " "                                     + arr[l] +                                     " "                       
                                                 + arr[r]);                       
                                                 l++;                       
                                                 r--;                       
                                                 }                       
           
                                                 // If sum of three elements                       
                                                 // is less than 'sum' then                       
                                                 // increment in left                       
                                                 else                                     if                                     (x + arr[l] + arr[r] < sum)                       
                                                 l++;                       
           
                                                 // if sum is greater than                       
                                                 // given sum, then decrement                       
                                                 // in right side                       
                                                 else                       
                                                 r--;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String args[])                       
                                                 {                       
                                                 int                                     [] arr =                                     new                                     int                                     [] {                                     0                                     , -                                     1                                     ,                                     2                                     , -                                     3                                     ,                                     1                                     };                       
                                                 int                                     sum = -                                     2                                     ;                       
                                                 int                                     n = arr.length;                       
                                                 findTriplets(arr, n, sum);                       
                                                 }                       
                         }                       
           
                         // This code is contributed                       
                         // by Akanksha Rai(Abby_akku)                       

Python3

                         # Python3 program to find triplets in a                       
                         # given array whose sum is given sum.                       
           
                         # function to print triplets with                       
                         # given sum                       
                         def                                     findTriplets(arr, n,                                     sum                                     ):                       
           
                                                 # 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]                                     =                                     =                                     sum                                     ) :                       
                                   
                                                 # print elements if it's sum                       
                                                 # is given sum.                       
                                                 print                                     (x, arr[l], arr[r]);                       
                                                 l                                     =                                     l                                     +                                     1                                     ;                       
                                                 r                                     =                                     r                                     -                                     1                                     ;                       
                                   
                                                 # If sum of three elements is less                       
                                                 # than 'sum' then increment in left                       
                                                 elif                                     (x                                     +                                     arr[l]                                     +                                     arr[r] <                                     sum                                     ):                       
                                                 l                                     =                                     l                                     +                                     1                                     ;                       
           
                                                 # if sum is greater than given sum,                       
                                                 # then decrement in right side                       
                                                 else                                     :                       
                                                 r                                     =                                     r                                     -                                     1                                     ;                       
                                   
                         # Driver code                       
                         arr                                     =                                     [                                     0                                     ,                                     -                                     1                                     ,                                     2                                     ,                                     -                                     3                                     ,                                     1                                     ];                       
                         sum                                     =                                     -                                     2                                     ;                       
                         n                                     =                                     len                                     (arr);                       
                         findTriplets(arr, n,                                     sum                                     );                       
           
                         # This code is contributed by                       
                         # Shivi_Aggarwal                       

C#

                         // C# program to find triplets                       
                         // in a given array whose sum                       
                         // is given sum.                       
                         using                                     System;                       
           
                         class                                     GFG {                       
           
                                                 // function to print                       
                                                 // triplets with given sum                       
                                                 static                                     void                                     findTriplets(                                     int                                     [] arr,                       
                                                 int                                     n,                                     int                                     sum)                       
                                                 {                       
                                                 // 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] == sum) {                       
                                                 // print elements if it's                       
                                                 // sum is given sum.                       
                                                 Console.WriteLine(x +                                     " "                                     + arr[l] +                                     " "                                     + arr[r]);                       
                                                 l++;                       
                                                 r--;                       
                                                 }                       
           
                                                 // If sum of three elements                       
                                                 // is less than 'sum' then                       
                                                 // increment in left                       
                                                 else                                     if                                     (x + arr[l] + arr[r] < sum)                       
                                                 l++;                       
           
                                                 // if sum is greater than                       
                                                 // given sum, then decrement                       
                                                 // in right side                       
                                                 else                       
                                                 r--;                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                                 static                                     int                                     Main()                       
                                                 {                       
                                                 int                                     [] arr =                                     new                                     int                                     [] { 0, -1, 2, -3, 1 };                       
                                                 int                                     sum = -2;                       
                                                 int                                     n = arr.Length;                       
                                                 findTriplets(arr, n, sum);                       
                                                 return                                     0;                       
                                                 }                       
                         }                       
           
                         // This code is contributed by rahul                       

PHP

                         <?php                       
                         // PHP program to find triplets                       
                         // in a given array whose sum                       
                         // is given sum.                       
           
                         // function to print triplets                       
                         // with given sum                       
                         function                                     findTriplets(                                     $arr                                     ,                                     $n                                     ,                                     $sum                                     )                       
                         {                       
                                                 // 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                                     ] ==                                     $sum                                     )                       
                                                 {                       
                                                 // print elements if it's                       
                                                 // sum is given sum.                       
                                                 echo                                     $x                                     ,                                     " "                                     ,                                     $arr                                     [                                     $l                                     ],                       
                                                 " "                                     ,                                     $arr                                     [                                     $r                                     ],                                     ""                                     ;                       
                                                 $l                                     ++;                       
                                                 $r                                     --;                       
                                                 }                       
           
                                                 // If sum of three elements                       
                                                 // is less than 'sum' then                       
                                                 // increment in left                       
                                                 else                                     if                                     (                                     $x                                     +                                     $arr                                     [                                     $l                                     ] +                       
                                                 $arr                                     [                                     $r                                     ] <                                     $sum                                     )                       
                                                 $l                                     ++;                       
           
                                                 // if sum is greater                       
                                                 // than given sum, then                       
                                                 // decrement in right side                       
                                                 else                       
                                                 $r                                     --;                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Driver code                       
                         $arr                                     =                                     array                                     (0, -1, 2, -3, 1);                       
                         $sum                                     = -2;                       
                         $n                                     = sizeof(                                     $arr                                     );                       
                         findTriplets(                                     $arr                                     ,                                     $n                                     ,                                     $sum                                     );                       
           
                         // This code is contributed by ajit                       
                         ?>                       

Javascript

                         <script>                       
                                                 // Javascript program to find triplets                       
                                                 // in a given array whose sum                       
                                                 // is given sum.                       
                                   
                                                 // function to print                       
                                                 // triplets with given sum                       
                                                 function                                     findTriplets(arr, n, sum)                       
                                                 {                       
                                   
                                                 // sort array elements                       
                                                 arr.sort(                                     function                                     (a, b){                                     return                                     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] == sum)                       
                                                 {                       
                                   
                                                 // print elements if it's                       
                                                 // sum is given sum.                       
                                                 document.write(x +                                     " "                                     + arr[l] +                                     " "                                     + arr[r] +                                     "</br>"                                     );                       
                                                 l++;                       
                                                 r--;                       
                                                 }                       
                                   
                                                 // If sum of three elements                       
                                                 // is less than 'sum' then                       
                                                 // increment in left                       
                                                 else                                     if                                     (x + arr[l] + arr[r] < sum)                       
                                                 l++;                       
                                   
                                                 // if sum is greater than                       
                                                 // given sum, then decrement                       
                                                 // in right side                       
                                                 else                       
                                                 r--;                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 let arr = [ 0, -1, 2, -3, 1 ];                       
                                                 let sum = -2;                       
                                                 let n = arr.length;                       
                                                 findTriplets(arr, n, sum);                       
                                   
                                                 // This code is contributed by rameshtravel07.                       
                         </script>                       

输出：

-3 -1 2-3 0 1

复杂性分析：

时间复杂性： O（n） ^2. ). 使用嵌套循环（一个用于迭代，另一个用于双指针技术）将时间复杂度提高到O（n） ^2. ).
辅助空间： O（1）。因为没有使用额外的数据结构。

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

THE END

技术文章