本文概述给定一系列不同的元素。任务是在总和为零的数组中查找三元组。
例子 ：
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 = 0Input : arr[] = {1, -2, 1, 0, 5}
Output : 1 -21
Explanation : The triplets with zero sum is
1 + -2 + 1 = 0推荐：请在"实践首先, 在继续解决方案之前。方法1：这是一个简单的方法, 需要O(n3)的时间得出结果。
方法：
天真的方法会运行三个循环, 并一一检查三个元素的总和是否为零。如果三个元素的总和为零, 则打印元素, 否则找不到打印。
【算法设计（找到所有零和的三元组）】算法：
- 使用循环计数器运行三个嵌套循环一世, j, k
- 这三个循环从0到n-3, 第二个循环从i + 1到n-2, 第三个循环从j + 1到n-1。循环计数器代表三元组的三个元素。
- 检查第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 SemwalPython3
# 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 SemwalC#
// 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)。
由于不需要额外的空间, 因此时间复杂度是恒定的。
方法：
这涉及遍历数组。对于每个元素arr [i], 找到一对总和为" -arr [i]"的对。这个问题简化为成对和, 可以使用哈希在O(n)时间内解决。
算法：
- 创建一个哈希来存储键值对。
- 运行带有两个循环的嵌套循环, 外循环从0到n-2, 内循环从i + 1到n-1
- 检查哈希图中是否存在第ith个元素和第j个元素的和与-1相乘
- 如果该元素存在于哈希图中, 则打印三元组, 否则将第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
{
s.add(arr[j]);
}
}
}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-JiPython3
# Python3 program to find triplets
# in a given array whose sum is zero # function to print triplets with 0 sum
def findTriplets(arr, n):
found = False
for i in range (n - 1 ):# Find all pairs with sum
# equals to "-arr[i]"
s = set ()
for j in range (i + 1 , n):
x = - (arr[i] + arr[j])
if x in s:
print (x, arr[i], arr[j])
found = True
else :
s.add(arr[j])
if found = = False :
print ( "No Triplet Found" )# Driver Code
arr = [ 0 , - 1 , 2 , - 3 , 1 ]
n = len (arr)
findTriplets(arr, n)# This code is contributed by Shrikant13C#
// 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
{
s.Add(arr[j]);
}
}
}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)。 - 辅助空间：上)。
由于需要一个哈希图, 因此时间复杂度是线性的。
方法：
上述方法需要额外的空间。这个想法是基于方法2
这个
发布。对于每个元素, 检查是否存在一对总和等于该元素的负值的对。
算法：
- 以升序对数组进行排序。
- 从头到尾遍历数组。
- 对于每个索引一世, 创建两个变量l =我+ 1和r = n – 1
- 循环运行直到l小于r, 如果array [l], array [r]的总和等于零, 则打印三元组并中断循环
- 如果总和小于零, 则增加l的值, 通过增加l的值, 总和将随着数组的排序而增加, 因此数组[l + 1]> 数组[l]
- 如果总和大于零, 那么递减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
// Javaprogram 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 - = 1if (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 SemwalC#
// 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), 不需要额外的空间, 因此时间复杂度是恒定的。
推荐阅读
- AngularJS 表格table用法代码示例
- 如何使用jQuery更改占位符文本（）
- 细说如何运用u盘安装win10
- 教你怎样查看u盘读写速度是多少
- 告诉你如何制作u盘打开盘
- 本文教您u盘缩水后怎样修好
- 本文详细说明怎样制作u盘打开盘
- 本文详细说明怎样把系统装在u盘
- 本文教您u盘提示格式化怎样修好