3Sum Leetcode шийдэл


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Adobe Амазоны Apple-ийн Bloomberg Facebook-ийн Google-ийн Microsoft- Oracle-ийн Tesla VMware
Array Хоёр заагч

Асуудлын мэдэгдэл

Өгсөн массив 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) тэгшитгэлийг ашиглан c-ийн утгыг олох боломжтой гэж үзье. a + b).

хэрэв бид бүх боломжит (a, b) хосыг авбал гогцоонд 2 үүрлэсэн a, 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 * log (N)): бид бүх боломжит (a, b) хосыг авахын тулд хоёр гогцоонд ашиглаж, массив дотор - (a + b) байгаа эсэхийг мэдэхийн тулд Binary хайлтыг ашиглаж байна.

Сансрын нарийн төвөгтэй байдал 

O (N): бид өвөрмөц гурван ихэр авахын тулд багц ашиглаж байна.

Хандлага 2 (Хоёр заагч)

Үүнтэй ижил даалгаврыг хэрэгжүүлэх илүү сайн арга бол хоёр заагч бөгөөд үндсэн санаа нь а-г сонгоод дараа нь хоёр заагчийг ашиглан a + b + c = 0 байхаар b ба c-ийг олоорой.
b + c = a байхаар хоёр заагчийг шилжүүлэх хэрэгтэй.
төвөгтэй хэрэгжилтийг ашиглан бид багцыг ашиглахаас зайлсхийх боломжтой (үүнийг өвөрмөц болгоход ашигладаг байсан)
хандлагад байгаа гурван ихэр 1)

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): a-ийн утгыг олж авахын тулд гогцоонд нэгийг ашиглаж байгаа бөгөөд а-ийн утга бүрт O (N) хугацаа шаардагдах хоёр заагчийн хандлагыг ашиглан b, c хосыг (a + b + c = 0 байхаар) олно. нийт хугацааны нарийн төвөгтэй байдал нь O (N ^ 2) дараалалтай байдаг.

Сансрын нарийн төвөгтэй байдал 

O (N): бид хариултыг хадгалахын тулд вектор ашиглаж байна.