3 פתרון Leetcode  


רמת קושי בינוני
נשאל לעתים קרובות Adobe אמזון בעברית תפוח עץ בלומברג פייסבוק Google מיקרוסופט אורקל טסלה VMware
אלגוריתמים מערך קידוד ראיון אישי הוכחת ראיונות LeetCode LeetCodeSolutions שני מצביעים

הצהרת בעיה  

ניתנת מערך של n מספרים שלמים, האם ישנם אלמנטים a, b, c במספרים כך ש + + b + c = 0? מצא את כל השלישיות הייחודיות במערך שנותן את סכום האפס.
שים לב: שערכת הפתרונות לא יכולה להכיל שלישיות משוכפלות.

דוגמה

#1

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

הסבר:3 פתרון Leetcode

#2

[0]
[]

 

גישה 1 (כוח ברוט + חיפוש בינארי)  

עלינו למצוא שלישיות ייחודיות עם a + b + c = 0, נניח שאנחנו יודעים את הערך של a ו- b, בעזרת המשוואה (a + b + c = 0) נוכל למצוא את הערך של c, שהוא - ( a + b).

אם ניקח את כל הזוגות האפשריים (a, b), נוכל להשיג את כל זוגות a, b באמצעות 2 מקוננות לולאות. לאחר מכן, נוכל להשתמש בחיפוש בינארי כדי לדעת אם c = - (a + b) קיים במערך הנתון או לא.
אם היא קיימת אז השלישייה (a, b, - (a + b)) תהיה שלישייה אפשרית. באופן זה נקבל את כל השלישיות האפשריות עם + b + c = 0, אך עלינו למצוא את השלישיות הייחודיות,
לשם כך אנו יכולים להכניס את כל השלישיות האפשריות למבנה נתונים כלשהו (כלומר להגדיר) כדי לקבל שלישיות ייחודיות.

יישום לפתרון 3Sum Leetcode

תוכנית 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 * יומן (N)): אנו משתמשים בשניים מקוננים לולאות כדי לקבל את כל הצמד האפשרי (a, b) וחיפוש בינארי כדי לדעת אם - (a + b) קיים במערך או לא.

מורכבות בחלל 

עַל): אנו משתמשים בערכה כדי להשיג שלישיות ייחודיות.

גישה 2 (שני מצביעים)  

גישה טובה יותר לביצוע אותה משימה היא שתי מצביעים, הרעיון הבסיסי הוא שנבחר a ואז נשתמש בשתי מצביעים כדי למצוא את b ו- c כך ש- + b + c = 0.
עלינו להזיז את שתי המצביעות כך שנקבל b + c = a.
באמצעות יישום מסובך אנו יכולים להימנע משימוש בערכה (ששימשה לייחודיות)
שלישיות בגישה 1)

יישום לפתרון 3Sum Leetcode

תוכנית 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

מורכבות זמן

O (N ^ 2): אנו משתמשים באחד לולאות כדי לקבל ערכים של a, ולכל ערך של a, אנו מוצאים את הזוג b, c (כך ש + + b + c = 0) תוך שימוש בשתי מצביעים שלוקח זמן O (N). לכן מורכבות הזמן הכוללת היא בסדר גודל של O (N ^ 2).

ראה גם
הזמן הטוב ביותר לרכוש ולמכור פתרון מניות Leetcode II

מורכבות בחלל 

עַל): אנו משתמשים בווקטור לאחסון התשובה.