3Sum Leetcode шешімі  


Күрделілік дәрежесі орта
Жиі кіреді Adobe Amazon алма Bloomberg Facebook Google Microsoft Oracle Tesla VMware
алгоритмдер Array кодтау сұхбат сұхбат дайындау 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)  

біз a + b + c = 0 бірегей үштіктерді табуымыз керек, a және b мәндерін білеміз делік, (a + b + c = 0) теңдеуін пайдаланып, с-нің мәнін табуға болады, - a + b).

егер біз барлық мүмкін (а, b) жұптарын алсақ, циклдар үшін 2 кірістірілген а, b жұптарын ала аламыз. Осыдан кейін біз берілген массивте c = - (a + b) бар-жоғын білу үшін екілік іздеуді қолдана аламыз.
егер ол бар болса, онда үштік (a, b, - (a + b)) мүмкін үштік болады. осылайша біз барлық мүмкін үшемдерді + b + c = 0-мен аламыз, бірақ біз бірегей үшемдерді табуымыз керек,
бұл үшін біз барлық үштіктерді кейбір деректер құрылымына кіргізе аламыз (яғни жиынтықта) бірегей үштіктер алу үшін.

3Sum Leetcode шешіміне енгізу

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 шешімінің күрделілігін талдау

Уақыттың күрделілігі

O (N * N * журнал (N)): біз барлық ықтимал (a, b) жұптарын алу үшін циклдар үшін екі кірістіруді қолданамыз және массивте - (a + b) бар-жоғын білу үшін екілік іздеуді қолданамыз.

Ғарыштың күрделілігі 

O (N): біз бірегей үшем алу үшін жиынтықты қолданамыз.

2-тәсіл (екі көрсеткіш)  

Сол тапсырманы орындау үшін екі тәсіл керек, негізгі идея - а таңдап, содан кейін екі көрсеткішті қолданып, b және c-ді a + b + c = 0 болатындай етіп табамыз.
b + c = a болатындай екі көрсеткішті жылжыту керек.
күрделі іске асыруды қолдану арқылы біз жиынтықты қолданудан аулақ бола аламыз (ол бірегей болу үшін қолданылған)
тәсіл үштіктер)

3Sum Leetcode шешіміне енгізу

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 шешімінің күрделілігін талдау

Уақыттың күрделілігі

O (N ^ 2): біз а мәндерін алу үшін циклдар үшін біреуін қолданамыз, ал а-ның әрбір мәні үшін O (N) уақытты алатын екі көрсеткіштік тәсілдің көмегімен b, c жұбын табамыз (a + b + c = 0 болатындай). сондықтан уақыттың жалпы күрделілігі O (N ^ 2) ретіне ие болады.

Сондай-ақ, қараңыз
Stock II Leetcode шешімін сатып алу және сатудың ең жақсы уақыты

Ғарыштың күрделілігі 

O (N): біз жауапты сақтау үшін векторды қолданамыз.