برنامه پیدا کردن سه تایی ها با مجموع صفر — راهنمای کاربردی

یک آرایه از عناصر متمایز داده شده است. هدف پیدا کردن سه تایی‌هایی است که مجموع آن‌ها برابر با صفر است. برای درک بهتر مطلب، مثال زیر قابل توجه است.

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 است. الگوریتم این روش، در ادامه آورده شده است.

  1. مرتب‌سازی همه عناصر آرایه
  2. اجرای حلقه از i=0 تا n-2
    • مقداردهی ولیه دو متغیر اندیس l=i+1 و r=n-1
  3. تا هنگامی که l < r
    • بررسی کن که آیا مجموع arr[l]‎ ،arr[i]‎ و arr[r]‎ برابر با صفر است یا خیر؛ اگر برابر با صفر است، سه‌تایی را چاپ، l++‎ و r–‎ کن.
  4. اگر مجموع، کمتر از صفر است، l++‎ کن.
  5. اگر مجموع، بزرگ‌تر از صفر است، r–‎ کن.
  6. اگر سه تایی با ویژگی بیان شده در آرایه وجود نداشت، «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)‎ است.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

منبع [+]

یک ستارهدو ستارهسه ستارهچهار ستارهپنج ستاره (No Ratings Yet)
Loading...

پاسخی بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *