3Sum Solution Leetcode  


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Adobe Amazon себ Блумберг Facebook Google Microsoft Oracle Tesla VMware
алгоритмҳо тартиботи ҳарбӣ рамзгузорӣ мусоҳиба омодасозии мусоҳиба LeetCode LeetCodeSolutions Ду нишоннамо

Изҳороти мушкилот  

Дода шудааст асал аз n адад, оё дар ададҳо унсурҳои a, b, c вуҷуд доранд, ки a + b + c = 0? Дар массив ҳамаи сегоникҳои беназирро ёбед, ки ҷамъи сифрро медиҳанд.
Аҳамият диҳед: маҷмӯи ҳалли масъала сегонаҳои такрорӣ набошад.

мисол

#1

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

Шарҳ:3Sum Solution Leetcode

#2

[0]
[]

 

Муносибати 1 (Brute Force + Search Binary)  

мо бояд сегоникҳои беназирро бо + b + c = 0 ёбем, бигӯем, ки арзиши a ва b-ро медонем, бо истифода аз муодилаи (a + b + c = 0), арзиши c -ро ёфтан мумкин аст, ки - а + б).

агар ҳамаи ҷуфтҳои имконпазири (a, b) -ро гирем, мо метавонем ҳамаи ҷуфтҳои a, b -ро бо истифода аз 2 барои лӯлаҳо дохил кунем. пас аз он, мо метавонем аз ҷустуҷӯи дуӣ истифода барем, то бидонем, ки c = - (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

Мураккабии вақт

O (N * N * log (N)): мо ду давраро барои ҳалқаҳо истифода мебарем, то ҳамаи ҷуфти имконпазир (а, б) ва ҷустуҷӯи дуӣ барои донистани он ки ((a + b) дар массив вуҷуд дорад ё не).

Мураккабии фазо 

О (Н): мо маҷмӯаро барои ба даст овардани сегоникҳои беназир истифода мебарем.

Муносибати 2 (Ду нишондиҳанда)  

Усули беҳтаре барои иҷрои як вазифа ду нишондиҳанда аст, ғояи асосӣ ин аст, ки мо a -ро интихоб карда, баъд ду нишондиҳандаро барои ёфтани 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

Мураккабии вақт

О (N ^ 2): мо якеро барои ҳалқаҳо барои гирифтани а истифода мебарем ва барои ҳар як арзиши а, ҷуфти b, c (ба тавре ки a + b + c = 0) -ро бо истифода аз ду равиши нишоннамо, ки вақти O (N) -ро мегирад, меёбем. пас мураккабии умумии вақт бо тартиби O (N ^ 2) мебошад.

ҳамчунин нигаред
Вақти беҳтарин барои харидан ва фурӯхтан Stock II Leetcode Solution

Мураккабии фазо 

О (Н): мо векторро барои нигоҳ доштани ҷавоб истифода мебарем.

1