برنامه پیدا کردن سه تایی ها با مجموع صفر — راهنمای کاربردی
یک آرایه از عناصر متمایز داده شده است. هدف پیدا کردن سه تایی‌هایی است که مجموع آن‌ها برابر با صفر است. برای درک بهتر مطلب، مثال زیر قابل توجه است.
Input : arr[] = {0, -1, 2, -3, 1}
Output : 0 -1 1
۲ -۳ ۱
Input : arr[] = {1, -2, 1, 0, 5}
Output : 1 -2 1
روش اول (ساده و از درجه O(n3))
این روش ساده از درجه زمانی O(n3) است. در این راهکار ساده برای حل این مسئله آن است که سه حلقه تو در تو اجرا شوند و یک به یک بررسی شود که آیا مجموع سه عنصر برابر با صفر است یا خیر. در صورتی که مجموع سه عنصر برابر با صفر باشد، عنصر چاپ و در غیر این صورت، پیغام «.Not Found» (پیدا نشد.) چاپ می‌شود.
پیاده‌سازی روش ساده در سی‌پلاس‌پلاس
// 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;
}پیاده‌سازی روش ساده در جاوا
// 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پیاده‌سازی روش ساده در پایتون ۳
# 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پیاده‌سازی روش ساده در سی‌شارپ
// 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]
== ۰)
{
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
// 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
?>روش ۲ (درهم‌سازی و از درجه O(n2))
در دومین روش، از پردازش هش کردن برای رسیدن به نتیجه استفاده می‌شود و تکرار در هر عنصر انجام می‌شود و کل پردازش‌ها در زمان کمتری نسبت به روش ساده انجام می‌شود و از درجه زمانی (O(n2 است. برای هر عنصر arr[i]، جفتی با مجموع -arr[i] پیدا می‌شود. این مساله، به مجموع جفت‌ها کاهش پیدا می‌کند و با استفاده از درهم‌سازی در زمان O(n) قابل انجام است.
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++ 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 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-Jiپیاده‌سازی روش درهم‌سازی در پایتون ۳
# Python3 program to find triplets
# in a given array whose sum is zero
# function to print triplets with 0 sum
def findTriplets(arr, n):
found = False
for i in range(n - 1):
# Find all pairs with sum
# equals to "-arr[i]"
s = set()
for j in range(i + 1, n):
x = -(arr[i] + arr[j])
if x in s:
print(x, arr[i], arr[j])
found = True
else:
s.add(arr[j])
if found == False:
print("No Triplet Found")
# Driver Code
arr = [0, -1, 2, -3, 1]
n = len(arr)
findTriplets(arr, n)
# This code is contributed by Shrikant13پیاده‌سازی روش درهم‌سازی در سی‌شارپ
// C# 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خروجی قطعه کد بالا، به صورت زیر است.
-۱ ۰ ۱ -۳ ۲ ۱
پیچیدگی زمانی این روش از درجه O(n2) و پیچیدگی فضایی آن از درجه O(n) است.
روش ۳ (مرتب‌سازی و از درجه O(n2))
روش هش که در بالا معرفی شده است، نیاز به فضای اضافی دارد. می‌توان این مسئله را با فضای کمکی از درجه O(1) حل کرد. در این روش از مرتب‌سازی برای رسیدن به نتیجه درست استفاده می‌شود و الگوریتم از مرتبه (O(n2 است. الگوریتم این روش، در ادامه آورده شده است.
- مرتب‌سازی همه عناصر آرایه
- اجرای حلقه از i=0 تا n-2
- مقداردهی ولیه دو متغیر اندیس l=i+1 و r=n-1
- تا هنگامی که l < r
- بررسی کن که آیا مجموع arr[l] ،arr[i] و arr[r] برابر با صفر است یا خیر؛ اگر برابر با صفر است، سه‌تایی را چاپ، l++ و r– کن.
- اگر مجموع، کمتر از صفر است، l++ کن.
- اگر مجموع، بزرگ‌تر از صفر است، r– کن.
- اگر سه تایی با ویژگی بیان شده در آرایه وجود نداشت، «Not Found.» را چاپ کن.
پیاده‌سازی روش سوم در سی‌پلاس‌پلاس
// 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 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..
}پیاده‌سازی روش سوم در پایتون
# 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# 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 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
?>خروجی قطعه کد بالا، به صورت زیر است.
-۳ ۱ ۲ -۱ ۰ ۱
پیچیدگی زمانی این روش از درجه O(n2) و پیچیدگی فضایی ان از درجه O(1) است.
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد می‌شوند:
- مجموعه آموزشهای برنامه‌‌‌نویسی
- آموزش ساختمان داده‌ها
- مجموعه آموزشهای ساختمان داده و طراحی الگوریتم
- یافتن دور همیلتونی با الگوریتم پس گرد — به زبان ساده
- الگوریتم بازی مار و پله همراه با کد — به زبان ساده
- حل مساله n وزیر با الگوریتم پس‌گرد (Backtracking) — به زبان ساده
منبع [+]
مجموعه: برنامه نویسی
Loading...