3Sum ලීට්කෝඩ් විසඳුම


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇෙබෝ ඇමේසන් Apple ජංගම දුරකථන බ්ලූම්බර්ග් ෆේස්බුක් ගූගල් මයික්රොසොෆ්ට් ඔරකල් ටෙස්ලා VMware
අරා පොයින්ටර් දෙකක්

ගැටළු ප්රකාශය

ලබා දී ඇත අරාව නිඛිල සංඛ්‍යා වල, a + b + c = 0 වැනි සංඛ්‍යා වල a, b, c මූලද්‍රව්‍ය තිබේද? ශුන්‍යයේ එකතුව ලබා දෙන අරාවෙහි ඇති අද්විතීය ත්‍රිත්ව සොයා ගන්න.
සැලකිල්ලට ගන්න: විසඳුම් කට්ටලයේ අනුපිටපත් ත්‍රිත්ව අඩංගු නොවිය යුතුය.

උදාහරණයක්

#1

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

පැහැදිලි කිරීම:3Sum ලීට්කෝඩ් විසඳුම

#2

[0]
[]

 

ප්‍රවේශය 1 (තිරිසන් බලය + ද්විමය සෙවීම)

අපට + b + c = 0 සමඟ අද්විතීය ත්‍රිත්ව සොයා ගැනීමට අවශ්‍යයි, අපි කියමු a සහ b වල අගය අපි දන්නවා, (a + b + c = 0) සමීකරණය භාවිතා කර අපට c හි අගය සොයාගත හැකිය, එනම් - ( a + b).

අපි හැකි සෑම (අ, ආ) යුගලයක් ගත්තොත්, අපට ලූප සඳහා කූඩු 2 ක් භාවිතා කරමින් a, b යුගල ලබා ගත හැකිය. ඊට පසු, අපට ලබා දී ඇති අරාවෙහි 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 ලීට්කෝඩ් විසඳුම සඳහා සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

O (N * N * log (N)): හැකි සෑම (අ, ආ) යුගලයක් සහ ද්විමය සෙවුමක් ලබා ගැනීම සඳහා අපි ලූප සඳහා කූඩු දෙකක් භාවිතා කරමු - (a + b) අරාවෙහි තිබේද නැද්ද යන්න දැන ගැනීමට.

අභ්‍යවකාශ සංකීර්ණතාව 

මත): අපි අද්විතීය ත්‍රිත්ව ලබා ගැනීමට කට්ටලයක් භාවිතා කරමු.

ප්‍රවේශය 2 (දර්ශක දෙකක්)

එකම කාර්යය කිරීමට වඩා හොඳ ප්‍රවේශයක් වන්නේ දර්ශක දෙකකි, මූලික අදහස නම් අපි a තෝරා ඉන්පසු b සහ c සොයා ගැනීමට දර්ශක දෙකක් භාවිතා කර + 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 ලීට්කෝඩ් විසඳුම සඳහා සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (එන් ^ 2): අපි a හි අගයන් ලබා ගැනීම සඳහා ලූප සඳහා එකක් භාවිතා කරන අතර, a හි සෑම අගයක් සඳහාම, O (N) කාලය ගතවන දර්ශක ප්‍රවේශ දෙකක් භාවිතා කරමින් b, c (a + b + c = 0 වැනි) යුගලය අපට හමු වේ. එබැවින් මුළු කාල සංකීර්ණතාව O (N ^ 2) අනුපිළිවෙලින් වේ.

අභ්‍යවකාශ සංකීර්ණතාව 

මත): පිළිතුර ගබඩා කිරීම සඳහා අපි දෛශිකයක් භාවිතා කරමු.