ශුන්‍ය එකතුවක් සහිත සියලුම ත්‍රිත්ව සොයා ගන්න


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇමේසන් GE සෞඛ්යාරක්ෂණය ගූගල් ඉහළ දැමීම
අරා හැෂ් සෙවීම් වර්ග කිරීම

“ශුන්‍ය එකතුවක් සහිත සියලු ත්‍රිත්වයන් සොයා ගන්න” යන ගැටලුවේ සඳහන් වන්නේ ඔබට ධනාත්මක හා negative ණ සංඛ්‍යා යන දෙකම අඩංගු අරාවක් ලබා දී ඇති බවයි. ගැටළු ප්‍රකාශය 0 ට සමාන ත්‍රිත්වයක් සොයා ගැනීමට අසයි.

ශුන්‍ය එකතුවක් සහිත සියලුම ත්‍රිත්ව සොයා ගන්න

උදාහරණයක්

arr[] = {0,-2,1,3,2,-1}
(-2 -1  3) (-2 0  2) (-1 0  1)

පැහැදිලි කිරීම

මේවා 0 හි ත්‍රිත්ව වේ.

(-2 + -1 + 3 = 0) (-2 + 0 + 2 = 0) (-1+ 0 + 1 = 0)

arr[] = {2,4,-5,-1,3}
(-5 2 3)

පැහැදිලි කිරීම

සංඛ්‍යා එකතුව 0 ⇒ -5 + 2 + 3 = 0 වන ත්‍රිත්ව වේ

ඇල්ගොරිතම

  1. වර්ග දී ඇති අරාව.
  2. සකසන්න බූලියන් විචල්ය හමු වී ඇත අසත්‍යයට.
  3. I = 0 සිට i දක්වා ලූප වීම
    1. කට්ටලයක් fir = i + 1, sec = n-1 තවත් විචල්යයක් x වත්මන් අරාව මූලද්‍රව්‍යයට.
    2. Fir අතර
      1. මූලද්රව්ය තුනක් එකට එකතු වී 0 ක් වේ දැයි පරීක්ෂා කරන්න.
        1. සත්‍ය නම්, අංක තුනම මුද්‍රණය කර සත්‍යය ලෙස සකසන්න.
      2. මූලද්‍රව්‍ය තුනක එකතුව (වත්මන් අරා මූලද්‍රව්‍ය) 0 ට වඩා අඩු දැයි පරීක්ෂා කරන්න.
        1. සත්‍ය නම්, fir හි අගය 1 කින් වැඩි කරන්න.
      3. මූලද්‍රව්‍ය තුනේ එකතුව 0 ට වඩා වැඩි දැයි පරීක්ෂා කරන්න.
          1. සත්‍ය නම් තත්පරයේ අගය 1 කින් අඩු කරන්න.
  4. IsFound අසත්‍යදැයි පරීක්ෂා කරන්න, එයින් අදහස් කරන්නේ ත්‍රිත්වයක් සෑදිය නොහැකි බවයි.

පැහැදිලි කිරීම

අපට අරාවක් ලබා දී ඇත. එවිට 0 හි ඇති අරාවෙහි දී ඇති සංඛ්‍යා සමඟ සෑදිය හැකි ත්‍රිත්වයන් තීරණය කිරීමට අපෙන් ඉල්ලා සිටිමු. අපි කූඩු ලූපයක් භාවිතා කිරීමට යන්නෙමු. මෙම ඇල්ගොරිතම නියත අවකාශයේ වැඩ කළ හැකිය. පළමුව, අපි අරාව වර්ග කිරීමට යන්නෙමු. මේ ආකාරයෙන් අපට ද්වි-පොයින්ටර් තාක්ෂණය භාවිතා කළ හැකිය. අපි එක් බූලියන් විචල්‍යයක් ප්‍රකාශයට පත් කර එහි වටිනාකම මුලින් අසත්‍ය ලෙස සකසමු. මෙය 0 හි මූලද්‍රව්‍ය එකතුවක් වන ත්‍රිත්ව කිසිවක් අපට සොයාගත නොහැකි දැයි සහතික කිරීම සඳහා පමණි හමු වී ඇත බොරු ලෙස පවතී. එවිට අපි ත්‍රිත්වයක් සොයාගත් සෑම විටම එය සත්‍යයට යාවත්කාලීන කරන්නෙමු. ඉතින් මේ සමඟ අපට නිගමනය කළ හැක්කේ ත්‍රිත්වයක් සොයාගත නොහැකි බවයි.

අපි පළමුව අරාව, කැදැලි ලූපය අනුව වර්ග කරමු. ඉන්පසු අපි අරාව n-1 දක්වා ගමන් කරමු. අපි ආරම්භක අගය i + 1 ලෙසත්, අවසාන අගය n-1 ලෙසත්, x පිටත ලූපයේ වත්මන් අගයටත් සකසමු. අභ්‍යන්තර පුඩුවේදී අපි අරාවක අගයන් හරහා ගමන් කර, මූලද්‍රව්‍ය තුනේම එකතුව (x + arr [fir] + arr [sec]) 0 ට සමානද නැද්ද යන්න පරීක්ෂා කරන්න. එය 0 බව සොයාගත හොත්, එයින් අදහස් වන්නේ අපි පළමු යුගලය සොයාගෙන අරාවෙහි වත්මන් සියලු අගයන් මුද්‍රණය කර isFound අගය සත්‍ය ලෙස සකසන්න.

මෙයින් ඇඟවෙන්නේ අපි යුගල වලින් එකක් සොයාගෙන ඇති බවයි. ත්රිත්වයේ එකතුව 0 ට සමාන නොවේ නම්, වත්මන් මූලද්රව්ය තුනක එකතුව 0 ට වඩා අඩු දැයි අපි පරීක්ෂා කරමු. එකතුව 0 ට වඩා අඩු නම්, අපි fir වැඩි කරන්නෙමු, එයින් අදහස් වන්නේ අපගේ ආරම්භක අගය වැඩි වී ඇති බවයි. තත්වය සෑහීමකට පත් නොවන්නේ නම්. එකතුව 0 ට වඩා වැඩි දැයි අපි පරීක්ෂා කරමු. සත්‍ය නම් තත්පර අඩුවීම.

මේ ආකාරයෙන්, 0 ට සමාන කළ හැකි සියලුම ත්‍රිත්වයන් අපි සොයා ගන්නෙමු.

ශුන්‍ය එකතුවක් සහිත සියලුම ත්‍රිත්ව සොයා ගැනීමට C ++ කේතය

#include<iostream>
#include<algorithm>

using namespace std;

void getTripletZero(int arr[], int n)
{
    bool isFound = false;
    sort(arr, arr+n);

    for (int i=0; i<n-1; i++)
    {
        int fir = i + 1;
        int sec = n - 1;
        int x = arr[i];
        while (fir < sec)
        {
            if (x + arr[fir] + arr[sec] == 0)
            {
                cout<<"("<<x<<" "<<arr[fir]<<" "<< arr[sec]<<")"<<endl;
                fir++;
                sec--;
                isFound = true;
            }
            else if (x + arr[fir] + arr[sec] < 0)
                fir++;
            else
                sec--;
        }
    }
    if (isFound == false)
        cout << " There is no triplet can be formed..!" << endl;
}
int main()
{
    int arr[] = {0,-2,1,3,2,-1};
    int n = sizeof(arr)/sizeof(arr[0]);
    getTripletZero(arr, n);
    return 0;
}
(-2 -1 3)
(-2 0 2)
(-1 0 1)

සියලු ත්‍රිත්ව ශුන්‍ය එකතුවක් සොයා ගැනීමට ජාවා කේතය

import java.util.Arrays;

class TripletSumzero
{
    public static void getTripletZero(int arr[], int n)
    {
        boolean isFound = false;

        Arrays.sort(arr);

        for (int i=0; i<n-1; i++)
        {
            int fir = i + 1;
            int sec = n - 1;
            int x = arr[i];
            while (fir < sec)
            {
                if (x + arr[fir] + arr[sec] == 0)
                {
                    System.out.println("(" + x + " "+arr[fir]+ " "+" "+arr[sec]+")");
                    fir++;
                    sec--;
                    isFound = true;
                }
                else if (x + arr[fir] + arr[sec] < 0)
                    fir++;
                else
                    sec--;
            }
        }
        if (isFound == false)
            System.out.println(" There is no triplet can be formed..!");
    }
    public static void main (String[] args)
    {
        int arr[] = {0,-2,1,3,2,-1};
        int n =arr.length;
        getTripletZero(arr, n);
    }
}
(-2 -1  3)
(-2 0  2)
(-1 0  1)

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

මත2) එහිදී “N”  යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ. අපි O (n) කාලය සඳහා දායක වන දර්ශක තාක්ෂණය දෙකක් භාවිතා කරන බැවින්. නමුත් තාක්‍ෂණය O (n) කාලය සඳහා භාවිතා වේ. මේ අනුව ඇල්ගොරිතම O (n ^ 2) කාලය තුළ ක්‍රියාත්මක වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1) අමතර ඉඩක් අවශ්‍ය නොවන බැවින්.