Ар кандай үч массивден a + b + c = суммасы турган үч элементти тап


Кыйынчылык деңгээли орто
Көп суралган Amazon Databricks Directi JP Morgan Taxi4Sure Twilio Zoho
согуштук тизме таштанды Hashing

Үч Сум - маектештер жакшы көргөн көйгөй. Бул учурунда менден жеке суралган көйгөй Amazon маек. Ошентип, убакытты текке кетирбей, көйгөйгө жетели. Оң жана терс сандардан турган массив. Нөлгө / суммага чейинки үч санды өзгөртүүгө болот, каалаган бүтүндөй сандын жыйынтыгын чыгарууга же үч массивден үч элементти табууга болот, а + b + с = сумма.

мисал

кирүү

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

продукция

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

Аны кантип чечсе болот?

Бул менин окурмандарым үчүн чоң азап болуп кала электе. Мага бир нерсени чагылдырган кичинекей псевдокод аркылуу чуркап көрөйүн. Кадам-кадам:

  • Биринчиден түрү сандар.
  • Сорттоо сандарга алардын чоңдугуна жараша жетүүгө жардам берет.
  • Экинчиден, массивден бир элементти тандайбыз.
  • Үчүнчүдөн, эки элементти тандап алабыз, алар биринчи элемент менен жыйынтыктаганда нөлгө барабар болот.
  • Эгер сизде Деджа-Ву бар болсо, мага ишара кылайын.
  • The ЭКИ SUM problem.
  • Биринчи элементти оңдогондон кийин, калган эки элементти табуу үчүн массивдин үстүнөн чуркайбыз.
  • Биз эки учту алабыз.
  • Эки четинен алынган сумма каалагандан чоңураак болгон сайын, биз акыркы маанини азайтабыз.
  • Эки четинен алынган сумма каалаганга караганда азыраак болгондо, биз баштапкы маанини көбөйтөбүз.
  • Эгерде сумма 0го жетсе, анда биз элементтерди жазабыз.
  • Акырында, элементтердин кайталанбашы үчүн ArrayList тизмесине кошулат.

Java Sum for Three Sum

class Solution 
{
    public List<List<Integer>> threeSum(int[] nums) 
    {
        Arrays.sort(nums);
        if(nums.length<3)
            return new ArrayList<>();
        Set<List<Integer>>lisa=new HashSet<>();
        for(int i=0;i<nums.length;i++)
        {
            int start=i+1;
            int end=nums.length-1;
            while(end>start)
            {
                int sum=nums[i]+nums[start]+nums[end];
                if(sum==0)
                {
                    List<Integer>cur=new ArrayList<Integer>();
                    cur.add(nums[i]);
                    cur.add(nums[start]);
                    cur.add(nums[end]);
                    lisa.add(cur);
                    end--;
                    start++;
                }
                else if(sum>0)
                    end--;
                else if(sum<0)
                    start++;
            }
        }
        return new ArrayList<>(lisa);
    }
}

C ++ коду үч суммага

class Solution 
{
public:
    vector<vector<int>> threeSum(vector<int>& nums)
    {
        sort(nums.begin(),nums.end());
        vector<vector<int>>ans;
        set<vector<int>>lisa;
        for(int i=0;i<nums.size();i++)
        {
            int start=i+1;
            int end=nums.size()-1;
            while(end>start)
            {
                int sum=nums[i]+nums[start]+nums[end];
                if(sum==0)
                {
                    lisa.insert({nums[i],nums[start],nums[end]}); 
                    end--;
                    start++;
                }
                else if(sum>0)
                    end--;
                else if(sum<0)
                    start++;
            }
        }
        for(auto x:lisa)
        {
            ans.push_back(x);
        }
        return ans;
    }
};

Комплекстик анализ

Убакыт татаалдыгы = O (n ^ 2)

Космостун татаалдыгы = O (1)

Кандай?

Үч суммага убакыттын татаалдыгын талдоо

  • Биринчиден, биз оңдой турган биринчи элементти тапкандан кийин тышкы цикл аркылуу чуркайбыз.
  • Ички цикл.
  • Биринчи элементти алат.
  • Экинчи элементти аягынан тартып алат.
  • Андан да жаманы, биз биринчи элементтен акыркы элементке өтө башташыбыз мүмкүн.
  • Бул O (n ^ 2) убакыттын татаалдыгына алып келет

Үч сумманын мейкиндигинин татаалдыгын талдоо

  • Көз салып туруу үчүн бир нече гана өзгөрмө колдонобуз.
  • Ошентип, космос татаалдыгын O (1)

Small Tweak

Үч Сумдун көйгөйүн сактоочу бирдиктерин алмаштырсак кандай болот. Amazed !?

Эч нерсе эмес. Биз бир эле массивден үч башка массивди ээлейбиз. Эгер сиз дагы деле ала элек болсоңуз. Мага сыноо ишинин үлгүсүн сунуш кылайын.

кирүү

Массив1 = {1, 2, 3, 4, 5}

Массив2 = {2, 3, 6, 1, 2}

Array3 = {3, 2, 4, 5, -6}

продукция

ООБА

Бул жерде мүмкүн болгон үч эмдерди чагылдырган сүрөт

Үч сум

Көйгөйгө кантип кайрылууга болот

  • Биринчиден, биз каалаган эки массивден сумманын мүмкүн болгон бардык айкалыштарын чыгарууга аракет кылабыз.
  • Буга жетишүү үчүн эки илмек иштетебиз
  • Кайра кайталанбашы үчүн ушул айкалыштардын бардыгын топтомдо сактайбыз
  • Сумманын -ve мааниси үчүнчү массивде бар экендигин текшеребиз
  • Эгер ооба болсо, анда биз ооба деп жооп беребиз
  • Акыр-аягы, бардык массивдерди карап чыккандан кийин, эгер 0го жетпесек, анда false дегенди кайтарабыз

Java Sum for Three Sum

public class Main
{
    public static boolean Three(int a1[],int a2[],int a3[])
    {
        Set<Integer>store=new HashSet<Integer>();
        Set<ArrayList<Integer>>lisa=new HashSet<>();
        for(int i=0;i<a2.length;i++)
        {
            for(int j=0;j<a3.length;j++)
                store.add(a2[i]+a3[j]);
        }
        for(int i=0;i<a1.length;i++)
        {
            if(store.contains(-a1[i]))
            {
                return true;
            }
        }
        return false;
    }
    public static void main (String[] args) 
    { 
        int a1[] = { 1 , 2 , 3 , 4 , 5 }; 
        int a2[] = { -2 , 3 , 6 , 1 , 2 }; 
        int a3[] = { 3 , 2 , -4 , 5 , -6 }; 
          
        int n1 = a1.length; 
        int n2 = a2.length; 
        int n3 = a3.length; 
          
        System.out.println(Three(a1, a2, a3));
    } 
}

C ++ коду үч суммага

bool Three(int a1[],int a2[],int a3[])
    {
    int n1 = sizeof(a1) / sizeof(a1[0]); 
    int n2 = sizeof(a2) / sizeof(a2[0]); 
    int n3 = sizeof(a3) / sizeof(a3[0]); 
    set<int>store;
    for(int i=0;i<n2;i++)
    {
        for(int j=0;j<n3;j++)
            store.insert(a2[i]+a3[j]);
    }
    for(int i=0;i<n1;i++)
    {
        if(store.find(-a1[i])!=store.end())
        {
            return true;
        }
    }
    return false;
}
int main() 
{ 
    int a1[] = { 1 , 2 , 3 , 4 , 5 }; 
    int a2[] = { 2 , 3 , 6 , 1 , 2 }; 
    int a3[] = { 3 , 2 , 4 , 5 , 6 }; 
    cout<<Three(a1, a2, a3);
  
    return 0; 
}

Комплекстик анализ

Убакыт татаалдыгы = O (n ^ 2)

Кандай?

  • Экинчи массивден элементти табуу үчүн сырткы циклди иштетебиз.
  • Ички циклде үчүнчү массивден экинчи массив элементине элемент кошобуз.
  • Убакыттын татаалдыгы O (n ^ 2).
  • Кийинки цикл биринчи массивдеги элементти текшерет
  • Бул цикл үчүн убакыттын татаалдыгы = O (1)
  • Ушул кезге чейинки акыркы татаалдык = O (n ^ 2) + O (1) = O (n ^ 2)

Космостун татаалдыгы = O (n)

Кандай?

  • Бардык элементтерди сактоо үчүн топтомду колдонобуз
  • Бул O (n) убакыттын татаалдыгына алып келет