Complexity Analysis:
- Time Complexity : O(n2).
Only two nested loops are required, so the time complexity is O(n2). - Auxiliary Space : O(1), no extra space is required, so the time complexity is constant.
<?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
?>
Complexity Analysis:
- Time Complexity: O(n2).
Since two nested loops are required, so the time complexity is O(n2). - Auxiliary Space: O(n).
Since a hashmap is required, so the space complexity is linear.
<?php
// function to print triplets with 0 sum
function findTriplets($arr, $n)
{
$found = false;
for ( $i=0; $i<$n-1; $i++)
{
// Find all pairs with sum equals to
// "-arr[i]"
$s = array();
for ( $j=$i+1; $j<$n; $j++)
{
$x = -($arr[$i] + $arr[$j]);
if (in_array($x, $s))
{
echo "FOUND => $x, $arr[$i], $arr[$j] \n\r";
$found = true;
}
else
$s[] = $arr[$j];
}
}
if ($found == false)
echo " No Triplet Found" ;
}
// Driver code
function main()
{
$arr = array(0, -1, 2, -3, 1);
$n = count($arr);
findTriplets($arr, $n);
return 0;
}
main();
