3 ಸಮ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ  


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಡೋಬ್ ಅಮೆಜಾನ್ ಆಪಲ್ ಬ್ಲೂಮ್ಬರ್ಗ್ ಫೇಸ್ಬುಕ್ ಗೂಗಲ್ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಒರಾಕಲ್ ಟೆಸ್ಲಾ ವರೆ
ಅಲ್ಗಾರಿದಮ್ಗಳು ಅರೇ ಕೋಡಿಂಗ್ ಸಂದರ್ಶನ ಸಂದರ್ಶನ ಪೂರ್ವಭಾವಿ ಲೀಟ್‌ಕೋಡ್ LeetCodeSolutions ಎರಡು ಪಾಯಿಂಟರ್

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ  

ನೀಡಲಾಗಿದೆ ಸರಣಿ 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) ಅಸ್ತಿತ್ವದಲ್ಲಿದೆಯೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂದು ತಿಳಿಯಲು ನಾವು ಬೈನರಿ ಹುಡುಕಾಟವನ್ನು ಬಳಸಬಹುದು.
ಅದು ಅಸ್ತಿತ್ವದಲ್ಲಿದ್ದರೆ ತ್ರಿವಳಿ (ಎ, ಬಿ, - (ಎ + ಬಿ)) ಸಂಭವನೀಯ ತ್ರಿವಳಿ ಆಗಿರುತ್ತದೆ. ಈ ರೀತಿಯಾಗಿ, ನಾವು + 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 ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ * ಎನ್ * ಲಾಗ್ (ಎನ್)): ನಾವು ಸಾಧ್ಯವಿರುವ (ಎ, ಬಿ) ಜೋಡಿಯನ್ನು ಪಡೆಯಲು ಎರಡು ಗೂಡುಗಳನ್ನು ಬಳಸುತ್ತಿದ್ದೇವೆ ಮತ್ತು ತಿಳಿಯಲು ಬೈನರಿ ಹುಡುಕಾಟ - (ಎ + ಬಿ) ರಚನೆಯಲ್ಲಿ ಅಸ್ತಿತ್ವದಲ್ಲಿದೆಯೋ ಇಲ್ಲವೋ ಎಂದು ತಿಳಿಯಲು.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ 

ಒ (ಎನ್): ಅನನ್ಯ ತ್ರಿವಳಿಗಳನ್ನು ಪಡೆಯಲು ನಾವು ಒಂದು ಸೆಟ್ ಅನ್ನು ಬಳಸುತ್ತಿದ್ದೇವೆ.

ಅಪ್ರೋಚ್ 2 (ಎರಡು ಪಾಯಿಂಟರ್)  

ಒಂದೇ ಕಾರ್ಯವನ್ನು ಮಾಡಲು ಉತ್ತಮ ವಿಧಾನವೆಂದರೆ ಎರಡು ಪಾಯಿಂಟರ್‌ಗಳು, ಮೂಲ ಕಲ್ಪನೆಯೆಂದರೆ ನಾವು ಒಂದು ಆಯ್ಕೆ ಮಾಡಿ ನಂತರ ಬಿ ಮತ್ತು ಸಿ ಅನ್ನು ಕಂಡುಹಿಡಿಯಲು ಎರಡು ಪಾಯಿಂಟರ್‌ಗಳನ್ನು ಬಳಸುತ್ತೇವೆ ಅಂದರೆ ಎ + ಬಿ + ಸಿ = 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) ನ ಕ್ರಮದಲ್ಲಿದೆ.

ಸಹ ನೋಡಿ
ಸ್ಟಾಕ್ II ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವನ್ನು ಖರೀದಿಸಲು ಮತ್ತು ಮಾರಾಟ ಮಾಡಲು ಉತ್ತಮ ಸಮಯ

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ 

ಒ (ಎನ್): ಉತ್ತರವನ್ನು ಸಂಗ್ರಹಿಸಲು ನಾವು ವೆಕ್ಟರ್ ಅನ್ನು ಬಳಸುತ್ತಿದ್ದೇವೆ.

1