3 סום לעעטקאָדע סאַלושאַן  


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַדאָובי אַמאַזאָן עפּל בלומבערג facebook גוגל מייקראָסאָפֿט אָראַקל טעסלאַ וומוואַרע
אַלגערידאַמז מענגע קאָדירונג אינטערוויו interviewprep LeetCode LeetCodeSolutions צוויי טייַטל

פּראָבלעם סטאַטעמענט  

געגעבן אַן מענגע פון n גאַנץ נומערן, זענען עס עלעמענטן a, b, c אין נומס אַזוי אַז a + b + c = 0? געפֿינען אַלע יינציק טריפּלאַץ אין די מענגע וואָס גיט די סומע פון ​​נול.
נאָטיץ: אַז די לייזונג שטעלן זאָל נישט אַנטהאַלטן דופּליקאַט טריפּלאַץ.

בייַשפּיל

#1

[-1,0,1,2,-1,4]
[[-1,0,1],[-1,-1,2]]

דערקלערונג:3 סום לעעטקאָדע סאַלושאַן

#2

[0]
[]

 

צוגאַנג 1 (ברוט פאָרס + ביינערי זוכן)  

מיר דאַרפֿן צו געפֿינען יינציק טריפּלאַץ מיט a + b + c = 0, לאָזן ס זאָגן מיר וויסן די ווערט פון a און b, ניצן די יקווייזשאַן (a + b + c = 0) מיר קענען געפֿינען די ווערט פון c, וואָס איז - ( אַ + ב).

אויב מיר נעמען אַלע מעגלעך (a, b) פּערז, מיר קענען באַקומען אַלע פּערז פון a, b ניצן 2 נעסטעד פֿאַר לופּס. נאָך דעם, מיר קענען נוצן ביינערי זוכן צו וויסן אויב c = - (a + b) יגזיסץ אין די געגעבן מענגע אָדער נישט.
אויב עס יגזיסץ, די טריפּלעט (a, b, - (a + b)) איז אַ מעגלעך טריפּלאַץ. אין דעם וועג, מיר וועלן באַקומען אַלע מעגלעך טריפּלאַץ מיט a + b + c = 0, אָבער מיר דאַרפֿן צו געפֿינען די יינציק טריפּלאַץ,
דערפֿאַר קענען מיר שטעלן אַלע די מעגלעך טריפּלאַץ אין עטלעכע דאַטן סטרוקטור (הייסט שטעלן) צו באַקומען יינציק טריפּלאַץ.

ימפּלאַמענטיישאַן פֿאַר 3 סום לעעטקאָדע סאַלושאַן

C ++ פּראָגראַם

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
        set<vector<int>> s;//to get unique triplets
        sort(nums.begin(),nums.end());
        int n=nums.size();
        vector<int> temp;
        temp.resize(3);
        for(int i=0;i<n;i++)
            for(int j=i+1;j<n;j++)
            {
                if(binary_search(nums.begin()+j+1,nums.end(),-nums[i]-nums[j])){
                     temp[0]=nums[i],temp[1]=nums[j],temp[2]=-nums[i]-nums[j];
                    sort(temp.begin(),temp.end());
                    //to get triplet in an order, will be easy to check if 
                    //duplicate exists or not
                    s.insert(temp);
                    }
            }
        vector<vector<int>> ans;
        for(auto triplet: s)
            ans.push_back(triplet);
        return ans;
}

void display_ans(vector<vector<int>> temp)
{
    for(auto triplet : temp) 
        cout<<triplet[0]<<" "<<triplet[1]<<" "<<triplet[2]<<"\n";
}

int main()
{
    vector<int> v{-1,0,1,2,-1,-4};
    display_ans(threeSum(v));
    return 0;
}
-1 -1 2 
-1 0 1

Java פּראָגראַם

import java.util.*;
class Rextester{
    
  static boolean binary_search(int l,int r,int[]nums, int x)
    {
        while(l<=r)
        {
            int mid=(l+r)/2;
            if(nums[mid]==x) return true;
            else if(nums[mid]>x) r=mid-1;
            else l=mid+1;
        }
        return false;
    }
    
    public static List<List<Integer>> threeSum(int[] nums) {
       
        List<List<Integer>> ans=new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        int n=nums.length;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(binary_search(j+1,n-1,nums,-(nums[i]+nums[j])))
                {
                    List<Integer> t=new  ArrayList<Integer>();
                    t.add(nums[i]);
                    t.add(nums[j]);
                    t.add(-(nums[i]+nums[j]));
                    ans.add(t);
                }
                
                while(j+1<n && nums[j+1]==nums[j]) j++;
            }
            
            while(i+1<n && nums[i+1]==nums[i]) i++;
        }
        
        return ans;  
    }
    
  public static void main(String args[])
    {
       	int[] nums={-1,0,1,2,-1,-4};
        for(List<Integer> list:  threeSum(nums))
        {
            for(int x: list)
            System.out.print(x+ " ");
            System.out.println();
        }
    }
}
-1 -1 2 
-1 0 1

קאַמפּלעקסיטי אַנאַליסיס פֿאַר 3 סום לעעטקאָדע סאַלושאַן

צייט קאַמפּלעקסיטי

אָ (N * N * קלאָץ (N)): מיר נוצן צוויי נעסטעד פֿאַר לופּס צו באַקומען אַלע די מעגלעך (a, b) פּאָר און אַ ביינערי זוכן צו וויסן אויב - (a + b) יגזיסץ אין די מענגע אָדער נישט.

ספעיס קאַמפּלעקסיטי 

אָ (N): מיר נוצן אַ סכום צו באַקומען יינציק טריפּלאַץ.

צוגאַנג 2 (צוויי טייַטל)  

א בעסערע צוגאַנג צו טאָן די זעלבע אַרבעט איז צוויי פּוינטערז, די גרונט געדאַנק איז אַז מיר סעלעקטירן a און נוצן צוויי פּוינטערז צו געפֿינען b און c אַזוי אַז a + b + c = 0.
מיר דאַרפֿן צו מאַך די צוויי פּוינטערז אַזוי אַז מיר באַקומען b + c = a.
ניצן טריקי ימפּלאַמענטיישאַן מיר קענען ויסמייַדן די נוצן פון שטעלן (וואָס איז געניצט צו באַקומען יינציק
טריפּלאַץ אין צוגאַנג 1)

ימפּלאַמענטיישאַן פֿאַר 3 סום לעעטקאָדע סאַלושאַן

C ++ פּראָגראַם

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
       vector<vector<int>> ans;
        sort(nums.begin(),nums.end());
        int n=nums.size();
        for(int i=0;i<n; i++)
        {
            int j=i+1,k=n-1;//two pointers
            while(j<n && j<k)
            {
                if(nums[j]+nums[k] == -nums[i])
                {
                    ans.push_back({nums[i],nums[j],nums[k]});
                    while(k!=0 && nums[k]==nums[k-1]) k--;//to avoid duplicates 
                    while(j!=n-1 && nums[j]==nums[j+1]) j++;
                    j++,k--;
                }
                else if(nums[j]+nums[k] > -nums[i]) 
                {
                    while(k!=0 && nums[k]==nums[k-1]) k--;
                    k--;
                }
                else
                {
                    while(j!=n-1 && nums[j]==nums[j+1]) j++;
                    j++;
                }
            }
            while(i!=n-1 && nums[i]==nums[i+1]) i++;
        }
        for(auto triplet : ans)
            sort(triplet.begin(),triplet.end());
        return ans;
}

void display_ans(vector<vector<int>> temp)
{
    for(auto triplet : temp) 
        cout<<triplet[0]<<" "<<triplet[1]<<" "<<triplet[2]<<"\n";
}

int main()
{
    vector<int> v{-1,0,1,2,-1,-4};
    display_ans(threeSum(v));
    return 0;
}
-1 -1 2 
-1 0 1

Java פּראָגראַם

import java.util.*;

class Rextester{
    
  public static List<List<Integer>> threeSum(int[] nums) {
       
        List<List<Integer>> ans=new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        int n=nums.length;
        
        for(int i=0;i<n;i++)
        {
            int p=i+1,q=n-1;
            while(p<q)
            {
                if(nums[p]+nums[q]==-nums[i])
                { //System.out.println(p+" "+q);
                    List<Integer> t=new ArrayList<Integer>();
                    t.add(nums[i]);
                    t.add(nums[p]);
                    t.add(nums[q]);
                 
                 ans.add(t);
                    
                    while(p+1<q &&  nums[p+1]==nums[p]) p++;
                    while(q-1>p &&  nums[q-1]==nums[q]) q--;
                    
                    p++; q--;
                }
                else if(nums[p]+nums[q] < -nums[i]) p++;
                else q--;
            }
            
            while(i+1<n && nums[i+1]==nums[i]) i++;
        }
        return ans;
    }
    
  public static void main(String args[])
    {
       	int[] nums={-1,0,1,2,-1,-4};
        for(List<Integer> list:  threeSum(nums))
        {
            for(int x: list)
            System.out.print(x+ " ");
            System.out.println();
        }
    }
}
-1 -1 2 
-1 0 1

קאַמפּלעקסיטי אַנאַליסיס פֿאַר 3 סום לעעטקאָדע סאַלושאַן

צייט קאַמפּלעקסיטי

אָ (N ^ 2): מיר נוצן איין פֿאַר לופּס צו באַקומען וואַלועס פון a, און פֿאַר יעדער ווערט פון a, מיר געפֿינען די פּאָר b, c (אַזאַ אַז a + b + c = 0) ניצן צוויי טייַטל צוגאַנג וואָס נעמט O (N) צייט. אַזוי גאַנץ צייט קאַמפּלעקסיטי איז פון די סדר פון O (N ^ 2).

זע אויך
בעסטער צייט צו קויפן און פאַרקויפן סטאק II לעעטקאָדע סאַלושאַן

ספעיס קאַמפּלעקסיטי 

אָ (N): מיר נוצן אַ וועקטאָר צו קראָם דעם ענטפער.

1