3 ਸਮ ਲੀਟਕੋਡ ਹੱਲ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਅਡੋਬ ਐਮਾਜ਼ਾਨ ਸੇਬ ਬਲੂਮਬਰਗ ਫੇਸਬੁੱਕ ਗੂਗਲ Microsoft ਦੇ ਓਰੇਕਲ Tesla VMware
ਅਰੇ ਦੋ ਪੁਆਇੰਟਰ

ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ

ਦਿੱਤਾ ਇੱਕ ਐਰੇ n ਪੂਰਨ ਅੰਕ ਦੇ, ਕੀ ਇੱਥੇ ਅੰਕਾਂ ਵਿਚ a, b, c ਅਜਿਹੇ ਹਨ ਜੋ a + b + c = 0 ਹਨ? ਐਰੇ ਵਿੱਚ ਸਾਰੀਆਂ ਵਿਲੱਖਣ ਤ੍ਰਿਪਤੀਆਂ ਲੱਭੋ ਜੋ ਸਿਫ਼ਰ ਦਾ ਜੋੜ ਦਿੰਦਾ ਹੈ.
ਨੋਟਿਸ: ਕਿ ਹੱਲ ਸੈੱਟ ਵਿੱਚ ਡੁਪਲਿਕੇਟ ਟ੍ਰਿਪਲਟਸ ਨਹੀਂ ਹੋਣੀਆਂ ਚਾਹੀਦੀਆਂ.

ਉਦਾਹਰਨ

#1

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

ਸਪਸ਼ਟੀਕਰਨ:3 ਸਮ ਲੀਟਕੋਡ ਹੱਲ

#2

[0]
[]

 

ਪਹੁੰਚ 1 (ਬਰੂਟ ਫੋਰਸ + ਬਾਈਨਰੀ ਸਰਚ)

ਸਾਨੂੰ ਇੱਕ + ਬੀ + ਸੀ = 0 ਦੇ ਨਾਲ ਵਿਲੱਖਣ ਤ੍ਰਿਪਤੀਆਂ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ, ਚਲੋ ਕਹਿੰਦੇ ਹਾਂ ਕਿ ਸਾਨੂੰ a ਅਤੇ b ਦੀ ਕੀਮਤ ਪਤਾ ਹੈ, ਸਮੀਕਰਨ (a + b + c = 0) ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹੋਏ, ਅਸੀਂ c ਦਾ ਮੁੱਲ ਪਾ ਸਕਦੇ ਹਾਂ, ਜੋ ਕਿ ਹੈ - ( ਏ + ਬੀ).

ਜੇ ਅਸੀਂ ਸਾਰੇ ਸੰਭਾਵਿਤ (ਏ, ਬੀ) ਜੋੜੇ ਲੈਂਦੇ ਹਾਂ, ਅਸੀਂ ਲੂਪਸ ਦੇ ਲਈ 2 ਨੇਸਟਡ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹੋਏ a, b ਦੇ ਸਾਰੇ ਜੋੜੇ ਪਾ ਸਕਦੇ ਹਾਂ. ਉਸ ਤੋਂ ਬਾਅਦ, ਅਸੀਂ ਇਹ ਜਾਣਨ ਲਈ ਬਾਈਨਰੀ ਖੋਜ ਦੀ ਵਰਤੋਂ ਕਰ ਸਕਦੇ ਹਾਂ ਕਿ ਦਿੱਤੇ ਐਰੇ ਵਿਚ c = - (a + b) ਮੌਜੂਦ ਹੈ ਜਾਂ ਨਹੀਂ.
ਜੇ ਇਹ ਮੌਜੂਦ ਹੈ ਤਾਂ ਤਿਕੋਣੀ (a, b, - (a + b)) ਇੱਕ ਸੰਭਾਵਤ ਤ੍ਰਿਕੋਣੀ ਹੋਵੇਗੀ. ਇਸ ਤਰੀਕੇ ਨਾਲ, ਅਸੀਂ ਏ + ਬੀ + ਸੀ = 0 ਨਾਲ ਸਾਰੇ ਸੰਭਾਵਿਤ ਤਿੰਨਾਂ ਪ੍ਰਾਪਤ ਕਰਾਂਗੇ, ਪਰ ਸਾਨੂੰ ਵਿਲੱਖਣ ਤ੍ਰਿਪਤੀਆਂ ਲੱਭਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ,
ਇਸਦੇ ਲਈ ਅਸੀਂ ਵਿਲੱਖਣ ਟ੍ਰਿਪਲਟਸ ਪ੍ਰਾਪਤ ਕਰਨ ਲਈ ਇਹ ਸਾਰੇ ਸੰਭਾਵਿਤ ਟ੍ਰਿਪਲਟਸ ਨੂੰ ਕੁਝ ਡਾਟਾ structureਾਂਚੇ (ਜਿਵੇਂ ਸੈਟ) ਵਿੱਚ ਸੰਮਿਲਿਤ ਕਰ ਸਕਦੇ ਹਾਂ.

3Sum ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਲਈ ਲਾਗੂਕਰਣ

ਸੀ ++ ਪ੍ਰੋਗਰਾਮ

#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

ਜਾਵਾ ਪ੍ਰੋਗਰਾਮ

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

3 ਸੂਮ ਲੀਟਕੋਡ ਹੱਲ ਲਈ ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ * ਐਨ * ਲੌਗ (ਐਨ)): ਅਸੀਂ ਲੂਪਸ ਦੇ ਲਈ ਦੋਵਾਂ ਦੀ ਵਰਤੋਂ ਕਰ ਰਹੇ ਹਾਂ ਸਭ ਸੰਭਾਵਿਤ (ਏ, ਬੀ) ਜੋੜਾ ਅਤੇ ਇਕ ਬਾਈਨਰੀ ਖੋਜ ਨੂੰ ਪ੍ਰਾਪਤ ਕਰਨ ਲਈ ਜੇ - (ਏ + ਬੀ) ਐਰੇ ਵਿਚ ਮੌਜੂਦ ਹੈ ਜਾਂ ਨਹੀਂ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ 

ਓ (ਐਨ): ਅਸੀਂ ਵਿਲੱਖਣ ਟ੍ਰਿਪਲਟਸ ਪ੍ਰਾਪਤ ਕਰਨ ਲਈ ਇੱਕ ਸੈੱਟ ਦੀ ਵਰਤੋਂ ਕਰ ਰਹੇ ਹਾਂ.

ਪਹੁੰਚ 2 (ਦੋ ਪੁਆਇੰਟਰ)

ਇਕੋ ਕੰਮ ਕਰਨ ਲਈ ਇਕ ਬਿਹਤਰ ਪਹੁੰਚ ਦੋ ਪੁਆਇੰਟਰ ਹਨ, ਮੁ ideaਲਾ ਵਿਚਾਰ ਇਹ ਹੈ ਕਿ ਅਸੀਂ ਇਕ ਦੀ ਚੋਣ ਕਰਦੇ ਹਾਂ ਅਤੇ ਫਿਰ ਬੀ ਅਤੇ ਸੀ ਲੱਭਣ ਲਈ ਦੋ ਪੁਆਇੰਟਰ ਵਰਤਦੇ ਹਾਂ ਜਿਵੇਂ ਕਿ ਇਕ + ਬੀ + ਸੀ = 0.
ਸਾਨੂੰ ਦੋ ਪੁਆਇੰਟਰ ਇਸ ਤਰਾਂ ਲਿਜਾਣ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਕਿ ਸਾਨੂੰ ਬੀ + ਸੀ = ਏ ਮਿਲਦਾ ਹੈ.
implementationਖੇ ਅਮਲ ਦੀ ਵਰਤੋਂ ਕਰਦਿਆਂ ਅਸੀਂ ਸੈੱਟ ਦੀ ਵਰਤੋਂ ਤੋਂ ਬਚ ਸਕਦੇ ਹਾਂ (ਜੋ ਕਿ ਵਿਲੱਖਣ ਪ੍ਰਾਪਤ ਕਰਨ ਲਈ ਵਰਤੀ ਜਾਂਦੀ ਸੀ)
ਪਹੁੰਚ 1 ਵਿੱਚ ਤਿੰਨੇ)

3Sum ਲੀਟਕੋਡ ਸਲਿ .ਸ਼ਨ ਲਈ ਲਾਗੂਕਰਣ

ਸੀ ++ ਪ੍ਰੋਗਰਾਮ

#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

ਜਾਵਾ ਪ੍ਰੋਗਰਾਮ

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

3 ਸੂਮ ਲੀਟਕੋਡ ਹੱਲ ਲਈ ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ ^ 2): ਅਸੀਂ ਏ ਦੇ ਮੁੱਲ ਪ੍ਰਾਪਤ ਕਰਨ ਲਈ ਲੂਪਾਂ ਲਈ ਇੱਕ ਦੀ ਵਰਤੋਂ ਕਰ ਰਹੇ ਹਾਂ, ਅਤੇ a ਦੇ ਹਰ ਮੁੱਲ ਲਈ, ਸਾਨੂੰ ਜੋੜਾ ਬੀ, ਸੀ (ਜਿਵੇਂ ਕਿ + + + + = =) ਦੋ ਪੁਆਇੰਟਰ ਪਹੁੰਚ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹਨ ਜੋ ਕਿ ਓ (ਐਨ) ਸਮਾਂ ਲੈਂਦਾ ਹੈ. ਇਸ ਲਈ ਕੁੱਲ ਸਮਾਂ ਗੁੰਝਲਤਾ O (N ^ 0) ਦੇ ਕ੍ਰਮ ਦੀ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ 

ਓ (ਐਨ): ਅਸੀਂ ਜਵਾਬ ਨੂੰ ਸਟੋਰ ਕਰਨ ਲਈ ਇਕ ਵੈਕਟਰ ਦੀ ਵਰਤੋਂ ਕਰ ਰਹੇ ਹਾਂ.