# 算法设计：找到所有零和的三元组

2021年3月15日09:42:22 发表评论 418 次浏览

## 本文概述

``````Input : arr[] = {0, -1, 2, -3, 1}
Output : (0 -1 1), (2 -3 1)

Explanation : The triplets with zero sum are
0 + -1 + 1 = 0 and 2 + -3 + 1 = 0

Input : arr[] = {1, -2, 1, 0, 5}
Output : 1 -2  1
Explanation : The triplets with zero sum is
1 + -2 + 1 = 0``````

## 推荐：请在"实践首先, 在继续解决方案之前。

1. 使用循环计数器运行三个嵌套循环一世, j, k
2. 这三个循环从0到n-3, 第二个循环从i + 1到n-2, 第三个循环从j + 1到n-1。循环计数器代表三元组的三个元素。
3. 检查第i, 第j, 第k个元素的总和是否等于零。如果是, 则打印总和, 否则继续。

## 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 = true ;
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 = true ;
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( "\n" );
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 = True
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 = true ;
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( "\n" );
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 = true;
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 ] , "\n" ;
\$found = true;
}
}
}
}

// If no triplet with 0
// sum found in array
if ( \$found == false)
echo " not exist " , "\n" ;

}

// Driver Code
\$arr = array (0, -1, 2, -3, 1);
\$n = sizeof( \$arr );
findTriplets( \$arr , \$n );

// This code is contributed by m_kit
?>``````

``````0 -1 1
2 -3 1``````

• 时间复杂度：上3)。
由于需要三个嵌套循环, 因此时间复杂度为O(n3)。
• 辅助空间：O(1)。
由于不需要额外的空间, 因此时间复杂度是恒定的。

1. 创建一个哈希来存储键值对。
2. 运行带有两个循环的嵌套循环, 外循环从0到n-2, 内循环从i + 1到n-1
3. 检查哈希图中是否存在第ith个元素和第j个元素的和与-1相乘
4. 如果该元素存在于哈希图中, 则打印三元组, 否则将第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\n" , 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\n" , x, arr[i], arr[j]);
found = true ;
}
else
{
}
}
}

if (found == false )
{
System.out.printf( " No Triplet Found\n" );
}
}

// 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 :
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}\n" , x, arr[i], arr[j]);
found = true ;
}
else
{
}
}
}

if (found == false )
{
Console.Write( " No Triplet Found\n" );
}
}

// 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``````

``````-1 0 1
-3 2 1``````

• 时间复杂度：上2)。
由于需要两个嵌套循环, 因此时间复杂度为O(n2)。
• 辅助空间：上)。
由于需要一个哈希图, 因此时间复杂度是线性的。

1. 以升序对数组进行排序。
2. 从头到尾遍历数组。
3. 对于每个索引一世, 创建两个变量l =我+ 1和r = n – 1
4. 循环运行直到l小于r, 如果array [l], array [r]的总和等于零, 则打印三元组并中断循环
5. 如果总和小于零, 则增加l的值, 通过增加l的值, 总和将随着数组的排序而增加, 因此数组[l + 1]>数组[l]
6. 如果总和大于零, 那么递减r的值, 通过增加l的值, 总和将随着数组的排序而减少, 因此array [r-1] <数组[r].

## 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\n" , 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 )
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 ], "\n" ;
\$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" , "\n" ;
}

// Driver Code
\$arr = array (0, -1, 2, -3, 1);
\$n = sizeof( \$arr );
findTriplets( \$arr , \$n );

// This code is contributed by ajit
?>``````

``````-3 1 2
-1 0 1``````

• 时间复杂度：上2)。
只需要两个嵌套循环, 因此时间复杂度为O(n2)。
• 辅助空间：O(1), 不需要额外的空间, 因此时间复杂度是恒定的。