Λύση 3Sum Leetcode  


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις πλίθα αμαζόνα μήλο Bloomberg Facebook Google Microsoft μαντείο Τέσλα VMware
αλγόριθμοι Παράταξη κωδικοποίησης συνέντευξη συνέντευξηprep LeetCode LeetCodeSolutions Δύο δείκτες

Δήλωση προβλήματος  

Δίνεται ένα παράταξη n ακέραιων αριθμών, υπάρχουν στοιχεία a, b, c σε αριθμούς έτσι ώστε a + b + c = 0; Βρείτε όλα τα μοναδικά τρίδυμα στον πίνακα που δίνει το άθροισμα του μηδέν.
Σημείωση: ότι το σύνολο λύσεων δεν πρέπει να περιέχει διπλότυπα τρίδυμα.

Παράδειγμα

#1

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

Επεξήγηση:Λύση 3Sum Leetcode

#2

[0]
[]

 

Προσέγγιση 1 (Brute Force + Binary Search)  

πρέπει να βρούμε μοναδικά τρίδυμα με + b + c = 0, ας πούμε ότι γνωρίζουμε την τιμή του a και b, χρησιμοποιώντας την εξίσωση (a + b + c = 0) μπορούμε να βρούμε την τιμή του c, που είναι - ( α + β).

αν πάρουμε όλα τα πιθανά ζεύγη (a, b), μπορούμε να πάρουμε όλα τα ζεύγη a, b χρησιμοποιώντας 2 ένθετα για βρόχους. μετά από αυτό, μπορούμε να χρησιμοποιήσουμε δυαδική αναζήτηση για να μάθουμε αν c = - (a + b) υπάρχει στον δεδομένο πίνακα ή όχι.
Εάν υπάρχει, τότε το τρίδυμο (a, b, - (a + b)) θα είναι πιθανό τρίδυμο. με αυτόν τον τρόπο, θα πάρουμε όλα τα πιθανά τρίδυμα με + b + c = 0, αλλά πρέπει να βρούμε τα μοναδικά τρίδυμα,
για αυτό μπορούμε να εισαγάγουμε όλα αυτά τα πιθανά τρίδυμα σε κάποια δομή δεδομένων (δηλαδή σετ) για να πάρουμε μοναδικά τρίδυμα.

Εφαρμογή για 3Sum Leetcode Solution

Πρόγραμμα 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

Ανάλυση πολυπλοκότητας για 3Sum Leetcode Solution

Χρόνος πολυπλοκότητας

O (N * N * log (N)): χρησιμοποιούμε δύο ένθετα για βρόχους για να πάρουμε όλο το δυνατό ζεύγος (a, b) και μια δυαδική αναζήτηση για να μάθουμε αν - (a + b) υπάρχει στον πίνακα ή όχι.

Διαστημική πολυπλοκότητα 

ΕΠΙ): χρησιμοποιούμε ένα σετ για να πάρουμε μοναδικά τρίδυμα.

Προσέγγιση 2 (Two Pointer)  

Μια καλύτερη προσέγγιση για να κάνετε το ίδιο έργο είναι δύο δείκτες, η βασική ιδέα είναι να επιλέξουμε ένα και στη συνέχεια να χρησιμοποιήσουμε δύο δείκτες για να βρούμε b και c έτσι ώστε a + b + c = 0.
πρέπει να μετακινήσουμε τους δύο δείκτες έτσι ώστε να πάρουμε b + c = a.
χρησιμοποιώντας δύσκολη εφαρμογή μπορούμε να αποφύγουμε τη χρήση του σετ (το οποίο χρησιμοποιήθηκε για να γίνει μοναδικό
τρίδυμα στην προσέγγιση 1)

Εφαρμογή για 3Sum Leetcode Solution

Πρόγραμμα 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

Ανάλυση πολυπλοκότητας για 3Sum Leetcode Solution

Χρόνος πολυπλοκότητας

Ο (Ν ^ 2): χρησιμοποιούμε ένα για βρόχους για να πάρουμε τιμές a, και για κάθε τιμή a, βρίσκουμε το ζεύγος b, c (έτσι ώστε a + b + c = 0) χρησιμοποιώντας προσέγγιση δύο δεικτών που παίρνει χρόνο O (N). έτσι η συνολική πολυπλοκότητα του χρόνου είναι της τάξης του O (N ^ 2).

Βλέπε επίσης
Καλύτερος χρόνος για αγορά και πώληση λιανικής Leetcode Solution II

Διαστημική πολυπλοκότητα 

ΕΠΙ): χρησιμοποιούμε ένα διάνυσμα για να αποθηκεύσουμε την απάντηση.

1