3 സം ലീറ്റ്കോഡ് പരിഹാരം


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ ആപ്പിൾ ബ്ലൂംബർഗ് ഫേസ്ബുക്ക് ഗൂഗിൾ മൈക്രോസോഫ്റ്റ് ഒറാക്കിൾ ടെസ്ല വിഎംവെയർ
അറേ രണ്ട് പോയിന്റർ

പ്രശ്നം പ്രസ്താവന

ഒരു നൽകി ശ്രേണി n സംഖ്യകളിൽ, a + b + c = 0 എന്ന സംഖ്യകളിൽ a, b, c ഘടകങ്ങൾ ഉണ്ടോ? പൂജ്യത്തിന്റെ ആകെത്തുക നൽകുന്ന അറേയിലെ എല്ലാ അദ്വിതീയ ട്രിപ്പിളുകളും കണ്ടെത്തുക.
ശ്രദ്ധിക്കുക: പരിഹാര സെറ്റിൽ തനിപ്പകർപ്പ് ത്രിമൂർത്തികൾ അടങ്ങിയിരിക്കരുത്.

ഉദാഹരണം

#1

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

വിശദീകരണം:3 സം ലീറ്റ്കോഡ് പരിഹാരം

#2

[0]
[]

 

സമീപനം 1 (ബ്രൂട്ട് ഫോഴ്സ് + ബൈനറി തിരയൽ)

ഒരു + b + c = 0 ഉള്ള അതുല്യമായ ത്രിവർണ്ണങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട്, a, b എന്നിവയുടെ മൂല്യം നമുക്കറിയാമെന്ന് പറയാം, സമവാക്യം ഉപയോഗിച്ച് (a + b + c = 0) നമുക്ക് c യുടെ മൂല്യം കണ്ടെത്താൻ കഴിയും, അതായത് - a + b).

സാധ്യമായ എല്ലാ (എ, ബി) ജോഡികളും എടുക്കുകയാണെങ്കിൽ, ലൂപ്പിനായി 2 നെസ്റ്റഡ് ഉപയോഗിച്ച് എ, ബി എന്നിവയുടെ എല്ലാ ജോഡികളും ലഭിക്കും. അതിനുശേഷം, തന്നിരിക്കുന്ന അറേയിൽ c = - (a + b) നിലവിലുണ്ടോ ഇല്ലയോ എന്ന് അറിയാൻ നമുക്ക് ബൈനറി തിരയൽ ഉപയോഗിക്കാം.
അത് നിലവിലുണ്ടെങ്കിൽ, ട്രിപ്പിൾ (a, b, - (a + b)) സാധ്യമായ ഒരു ട്രിപ്പിൾ ആയിരിക്കും. ഈ രീതിയിൽ, + b + c = 0 ഉപയോഗിച്ച് സാധ്യമായ എല്ലാ ത്രിമൂർത്തികളും നമുക്ക് ലഭിക്കും, പക്ഷേ നമുക്ക് അതുല്യമായ ത്രിമൂർത്തികൾ കണ്ടെത്തേണ്ടതുണ്ട്,
അതിനായി അദ്വിതീയമായ ത്രിമൂർത്തികൾ നേടുന്നതിന് സാധ്യമായ ഈ മൂന്നും ചില ഡാറ്റാ ഘടനയിൽ (അതായത് സെറ്റ്) ഉൾപ്പെടുത്താം.

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

3Sum Leetcode പരിഹാരത്തിനായുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N * N * ലോഗ് (N)): സാധ്യമായ എല്ലാ (എ, ബി) ജോഡികളും ലഭിക്കാൻ ഒരു ബൈനറി തിരയലും ലഭിക്കുന്നതിന് ഞങ്ങൾ രണ്ട് നെസ്റ്റഡ് ലൂപ്പുകൾ ഉപയോഗിക്കുന്നു - (a + b) അറേയിൽ ഉണ്ടോ ഇല്ലയോ എന്ന് അറിയാൻ.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (N): അദ്വിതീയ ട്രിപ്പിളുകൾ ലഭിക്കാൻ ഞങ്ങൾ ഒരു സെറ്റ് ഉപയോഗിക്കുന്നു.

സമീപനം 2 (രണ്ട് പോയിന്റർ)

ഒരേ ടാസ്ക് ചെയ്യുന്നതിനുള്ള ഒരു മികച്ച സമീപനം രണ്ട് പോയിൻറുകളാണ്, അടിസ്ഥാന ആശയം നമ്മൾ ഒരു തിരഞ്ഞെടുത്ത് രണ്ട് പോയിന്ററുകൾ ഉപയോഗിച്ച് b, c എന്നിവ കണ്ടെത്തുന്നതിന് a + b + c = 0.
നമുക്ക് b + c = a ലഭിക്കുന്ന രണ്ട് പോയിന്ററുകൾ നീക്കേണ്ടതുണ്ട്.
തന്ത്രപരമായ നടപ്പാക്കൽ ഉപയോഗിച്ച് നമുക്ക് സെറ്റിന്റെ ഉപയോഗം ഒഴിവാക്കാനാകും (അതുല്യമായത് നേടാൻ ഇത് ഉപയോഗിച്ചു
സമീപനത്തിലെ മൂന്നിരട്ടി 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

3Sum Leetcode പരിഹാരത്തിനായുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N ^ 2): A യുടെ മൂല്യങ്ങൾ‌ നേടുന്നതിനായി ഞങ്ങൾ‌ ലൂപ്പുകൾ‌ക്കായി ഒന്ന് ഉപയോഗിക്കുന്നു, ഒപ്പം a യുടെ ഓരോ മൂല്യത്തിനും O (N) സമയം എടുക്കുന്ന രണ്ട് പോയിന്റർ‌ സമീപനം ഉപയോഗിച്ച് b, c (a + b + c = 0 പോലുള്ള) ജോഡി കണ്ടെത്തുന്നു. അതിനാൽ മൊത്തം സമയ സങ്കീർണ്ണത O (N ^ 2) ന്റെ ക്രമത്തിലാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത 

O (N): ഉത്തരം സംഭരിക്കാൻ ഞങ്ങൾ ഒരു വെക്റ്റർ ഉപയോഗിക്കുന്നു.