Знайдзіце тры элементы з розных трох масіваў, такія што a + b + c = сума


Узровень складанасці серада
Часта пытаюцца ў амазонка Збор дадзеных Дырэкты JP Morgan Таксі4Упэўнена Twilio Zoho
масіў гашыш хэшавання

Three Sum - праблема, якую любяць інтэрв'юеры. Гэта праблема, пра якую мяне асабіста спыталі падчас амазонка сумоўе. Такім чынам, не губляючы больш часу, давайце падыдзем да праблемы. Масіў, які мае як дадатныя, так і адмоўныя лікі. Тры лікі, якія складаюць нуль /, могуць быць зменены, каб падвесці любую цэлую лічбу альбо знайсці трохэлемент з розных трох масіваў, так што a + b + c = sum.

Прыклад

уваход

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

выхад

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

Як вырашыць гэтую праблему?

Перш чым гэта стане большым болем для маіх чытачоў. Дазвольце мне прабегчыся па невялікім псеўдакодзе, які ілюструе тое самае. Крок за крокам:

  • Па-першае сартаваць лічбы.
  • Сартаванне дапамагае нам атрымаць доступ да лічбаў паводле іх велічыні.
  • Па-другое, мы выбіраем элемент з масіва.
  • Па-трэцяе, мы выбіраем два элементы, якія пры падвядзенні вынікаў з першым элементам дадуць нуль.
  • У выпадку, калі ў вас ёсць Deja Vu, дазвольце мне падказаць намёк.
  • ,en ДРУГАЯ Праблема 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)

Невялікая хітрасць

Што рабіць, калі мы зменім блокі захоўвання праблемы Three Sum. Здзіўлены !?

Нічога асаблівага. Мы проста возьмем тры розныя масівы, чым адзін. У выпадку, калі вы ўсё яшчэ не атрымалі яго. Дазвольце мне прадставіць узор тэставага прыкладу.

уваход

Масіў1 = {1, 2, 3, 4, 5}

Масіў2 = {2, 3, 6, 1, 2}

Масіў3 = {3, 2, 4, 5, -6}

выхад

ДА

Вось малюнак, які падкрэслівае магчымыя трайняты

Тры сумы

Як падысці да праблемы

  • Па-першае, мы спрабуем стварыць усе магчымыя камбінацыі сумы з любых двух масіваў.
  • Для гэтага мы праводзім дзве завесы
  • Усе гэтыя камбінацыі мы захоўваем у наборы, каб пазбегнуць паўтораў
  • Мы правяраем, ці даступна значэнне -ve сумы ў трэцім масіве
  • Калі так, то мы вяртаемся так
  • Нарэшце, нават пасля прагляду ўсіх масіваў, калі мы не дасягнем 0, мы вяртаем false

Код 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)