CP #11 : 3Sum Problemi

 Problem surada.

Cozum

Ilk akla gelen yine tum tripletleri uretmek ve duplikasyonlari da bir sekilde elimine ederek, toplamlari sifir olan tripletleri dondurmek. Bu da eger duplikasyon olayini O(1) ile cozebilirsek toplamda O(n3) gibi bir maliyet getirir ki, cok ciddi bir maliyet. 

Brute force olarak triplet uretmek, icsel olarak (implicit? :D) verilen array'in hicbir duzeni olmadigi bilgisini barindiriyor. Yani array elemanlari rastgele dizilmis ve biz de direk 3 dondu icerisinde hepsini donuyoruz. Ama requiremet'e bakarsak bize toplami sifir olan tripletler lazim. 

Bu ipuclari bize gosteriyor ki, verilen arrayi sort edersek, bir optimizasyon cikartabiliriz. Ne de olsa sort ettikten sonra arrayin traverse yonune gore toplami gerektigi gibi artirabilir ya da azaltabiliriz. 

Ornek olarak [-1,0,1,2,-1,-4,-2,-3,3,0,4] inputunu inceleyelim. Bunu sort ettigimiz zaman yukaridaki gibi bir sonuc elde ediyoruz. Tum array'i traverse edecek bir i index'ine yanci olarak bir soldan bir de sagdan elemanlar katarak, sifiri bulabiliriz. Bulamasak bile, j ve k indexleri ile nasil oynamamiz gerektigini bilebiliriz. Cunku ornek olarak burada i=0, j=1 ve k = 10 iken, toplam -3. -4'u icerecek (cunku i index'i sabit) bir toplam bulabilmek icin demek ki j'yi artirmamiz gerekiyor. 

Implementasyon

def threeSum(self, nums):

    # sonucta duplikasyon istenmedigi icin buldugumuz tripletleri 

    # bir set icerisinde tutacagiz

    hist = set()

    # i indexi 0'dan sona kadar gidecek ama k, ensondan baslayacahi icin

    # enson elemani k'ya ayiriyoruz

    for i in range(len(nums)-2):

        j = i + 1

        k = len(nums) - 1

        while j < k:

            smm = nums[i] + nums[j] + nums[k]

            

            if  smm == 0:

                # triplet icerisindeki sayilarin sirasi onemli olmadigi icin bir set teskil etmesi gerekiyor

                # ancak pythondaki standart set mutable oldugu icin hashlenemiyor ve de dolayisi ile set'e

                # eklenemiyor. biz zaten olusturulan tripleti mutate etmeyecegimiz icin 

                # frozenset kullanabiliriz

                hashed = frozenset([nums[i], nums[j], nums[k]])

                if hashed not in hist:

                    hist.add(hashed)

                # sifiri buldu isek, k'yi bir azaltip j'yi bir artirip, baska bir sifir kombinasyonu

                # bulabilir miyiz diye yola devam ediyoruz.

                k -= 1

                j += 1

            elif smm > 0:

                # eger sifirdan buyuk isek, k'yi azaltiyoruz ki daha dusuk bir sayi ile tekrar deneyelim

                k -= 1

            elif smm < 0:

                # eger sifirdan kucuk isek, j'yi artiriyoruz ki daha buyuk bir sayi ile tekrar deneyelim

                j += 1

    return list(hist)

Analiz

i indexi icin tum arrayi bir kere donuyoruz. Ayrica her bir i degeri icin de bastan ve sodan iki pointer ile liste ortasina kadar donuyoruz. Bu iki dongu de aslinda lineer ama ic ice olduklari icin O(n2) bir kompleksite elde etmis olsuyoruz. 

Hafiza gereksinimi de tripletleri hashset icerisnde tuttugumuz icin, verilen input ile lineer bir baglanti icerisinde ve O(n) denilebilir.