3Sum Leetcode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg Facebook google microsoft Kahin Tesla VMware
alqoritmlər Geyim kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions İki işarəBaxılıb 80

Problem bəyanat

Verilmiş bir array n tam ədədi, ədədə a, b, c elementləri var ki, a + b + c = 0? Sıfır cəmi verən bütün unikal üçqatları massivdə tapın.
Diqqət: həll dəstində təkrarlanan üçük olmamalıdır.

misal

#1

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

Explanation:3Sum Leetcode Həlli

#2

[0]
[]

 

Yanaşma 1 (Brute Force + Binary Search)

a + b + c = 0 ilə misilsiz üçüklər tapmalıyıq, deyək a və b-nin dəyərini bilirik, (a + b + c = 0) tənliyini istifadə edərək c dəyərini tapa bilərik - ( a + b).

bütün mümkün (a, b) cütləri götürsək, döngələr üçün 2 iç içə istifadə edərək bütün a, b cütlərini əldə edə bilərik. bundan sonra verilmiş massivdə c = - (a + b) mövcud olub olmadığını bilmək üçün ikili axtarışdan istifadə edə bilərik.
varsa, onda üçlük (a, b, - (a + b)) mümkün üçlük olacaqdır. bu şəkildə, + b + c = 0 ilə mümkün olan bütün üçükləri əldə edəcəyik, ancaq unikal üçlükləri tapmalıyıq,
bunun üçün unikal üçlüklər əldə etmək üçün bütün bu üçlüləri bəzi məlumat strukturuna (yəni dəst) daxil edə bilərik.

3Sum Leetcode Solution üçün tətbiqetmə

C ++ Proqramı

#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 Proqramı

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 Həlli üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (N * N * log (N)): bütün mümkün (a, b) cütlüyünü əldə etmək üçün döngələr üçün iki iç içə istifadə edirik və - (a + b) -nın massivdə olub olmadığını yoxlamaq üçün İkili axtarış aparırıq.

Kosmik Mürəkkəblik 

O (N): unikal üçəmlər əldə etmək üçün bir dəstdən istifadə edirik.

Yanaşma 2 (İki İşarəli)

Eyni tapşırığı yerinə yetirmək üçün daha yaxşı bir yanaşma iki göstəricidir, əsas fikir a seçirik və sonra b və c tapmaq üçün iki göstəricidən istifadə edirik ki, a + b + c = 0 olsun.
iki göstəricini elə hərəkət etdirməliyik ki, b + c = a əldə edək.
hiyləgər tətbiqetmədən istifadə edərək dəstin istifadəsindən çəkinə bilərik (unikal olmaq üçün istifadə olunurdu)
yanaşmada üçlər 1)

3Sum Leetcode Solution üçün tətbiqetmə

C ++ Proqramı

#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 Proqramı

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 Həlli üçün Mürəkkəblik Analizi

Zamanın mürəkkəbliyi

O (N ^ 2): a dəyərlərini almaq üçün döngələr üçün birini istifadə edirik və a hər dəyəri üçün O (N) vaxt aparan iki göstərici yanaşmadan istifadə edərək b, c cütlüyünü (a + b + c = 0 olduğu kimi) tapırıq. beləliklə ümumi zaman mürəkkəbliyi O (N ^ 2) sırasındadır.

Kosmik Mürəkkəblik 

O (N): cavabı saxlamaq üçün bir vektordan istifadə edirik.

Şərh yaz

Translate »
1