A + b + c = нийлбэр байхаар өөр гурван массиваас гурван элементийг ол


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны Өгөгдлийн сан Directi JP Morgan Такси4 Twilio Zoho
Array Хаш Хаширч байна

Гурван сум бол ярилцлага өгдөг хүмүүсийн хайрладаг асуудал юм. Энэ үеэр надаас асуусан асуудал юм Амазоны ярилцлага. Тиймээс цаг хугацаа алдалгүй асуудалд орцгооё. Эерэг ба сөрөг тоо бүхий массив. Тэг / хүртэл нэгтгэх гурван тоог өөрчилж болно, дурын бүхэл тоогоор нэгтгэх эсвэл гурван өөр массиваас a + b + c = нийлбэр байхаар гурван элемент олох боломжтой.

Жишээ нь

Оролт

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

гаралтын

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

Үүнийг хэрхэн шийдэх вэ?

Энэ нь миний уншигчдын хувьд илүү том өвдөлт болохоос өмнө. Үүнтэй ижил зүйлийг дүрсэлсэн жижиг псевдокодоор гүйж үзье. Алхам алхамаар:

  • Нэгдүгээрт хувь заяа тоонууд.
  • Эрэмбэлэх нь тоонуудын хэмжээг харгалзан үзэх боломжийг олгодог.
  • Хоёрдугаарт, бид массиваас элемент сонгоно.
  • Гуравдугаарт, бид хоёр элементийг сонгож, эхний элементтэй нэгтгэхэд тэг гарах болно.
  • Хэрэв танд Deja Vu байгаа бол надад нэг зөвлөгөө өгөхийг зөвшөөрнө үү.
  • The ХОЁРДУГААР SUM асуудал.
  • Эхний элементээ зассаны дараа массив дээгүүр гүйж нөгөө хоёр элементийг хайж олох болно.
  • Бид хоёр төгсгөлийг авдаг.
  • Хоёр төгсгөлийн нийлбэр нь хүссэн хэмжээнээс их байх болгонд бид эцсийн утгыг бууруулдаг.
  • Хоёр төгсгөлийн нийлбэр хүссэн хэмжээнээс бага байх бүрт бид эхлэх утгыг нэмэгдүүлдэг.
  • Хэрэв нийлбэр нь 0-д хүрвэл бид элементүүдийг тэмдэглэнэ.
  • Эцэст нь элементүүдийг ArrayList жагсаалтад нэмж дахин давтахгүй байхыг баталгаажуулна.

Гурван суманд зориулсан Java код

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) болгоно

Жижиг тохируулга

Гурван сумны асуудлын хадгалах нэгжийг өөрчлөх юм бол яах вэ. Гайхсан !?

Юмгүйдээ. Бид ганц нэгээс гурван өөр массивыг авах болно. Хэрэв та үүнийг авч чадаагүй бол. Туршилтын жишээг танилцуулъя.

Оролт

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

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

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

гаралтын

YES

Гурван ихэр байж болохыг онцолсон зураг энд байна

Гурван сум

Асуудалд хэрхэн хандах вэ

  • Нэгдүгээрт, бид аль ч массиваас нийлбэрийн бүх боломжит хослолыг гаргахыг хичээдэг.
  • Үүнийг хэрэгжүүлэхийн тулд бид хоёр гогцоо ажиллуулдаг
  • Бид эдгээр бүх хослолыг давтахаас зайлсхийхийн тулд багцад хадгалдаг
  • Нийлбэрийн -ve утга гурав дахь массивт байгаа эсэхийг шалгана
  • Хэрэв тийм бол бид тийм гэж хариулна
  • Эцэст нь бүх массивыг давтаж үзсэний дараа бид 0-д хүрэхгүй бол бид худал гэсэн утгатай болно

Гурван суманд зориулсан Java код

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) -ийн цаг хугацааны нарийн төвөгтэй байдалд хүргэдэг.