Leetcode 15 3Sum

Soru

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Örnek 1

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Örnek 2

Input: nums = []
Output: []

Çözüm

• Bu problem genellikle iki işaretçi yöntemi kullanılarak çözülür. Diziyi önce sıralayarak başlar, sonra her eleman için iki işaretçi (bir tanesi o elemandan hemen sonraki elemana, diğeri dizinin sonuna yerleştirilir) kullanarak toplamı sıfır olan üçlü kombinasyonları ararsınız. Çakışmaları ve tekrar eden üçlülerin oluşmasını engellemek için bazı kontroller yapılır.
• Çalışma Mekanizması:
• Diziyi Sırala: Dizi sıralanarak, iki işaretçi tekniklerinin uygulanabilmesi için hazır hale getirilir.
• Tekrar Eden Elemanların Atlaması: İlk for döngüsünde, tekrar eden elemanları atlayarak çözümde yalnızca benzersiz üçlülerin oluşmasını sağlar.
• İki İşaretçi Arama: İki işaretçi, mevcut elemanın bir sonraki elemanından başlayarak, dizinin sonuna kadar hareket eder. Üç elemanın toplamı sıfırsa bir çözüm olarak kaydedilir.
• Çakışmaları Önleme: Çözüm bulunduktan sonra, sol ve sağ işaretçiler tekrar eden değerleri atlayarak hareket ettirilir.
• Sonuç Döndürme: Tüm benzersiz çözümler bir liste olarak döndürülür.

Code

class Solution:
    def threeSum(self, nums):
        nums.sort()
        result = []
        for i in range(len(nums) - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue  # Aynı eleman üzerinde tekrar işlem yapmayı önle
            left, right = i + 1, len(nums) - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total == 0:
                    result.append([nums[i], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1  # Sol işaretçiyi tekrar eden elemanlar üzerinde hareket ettir
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1  # Sağ işaretçiyi tekrar eden elemanlar üzerinde hareket ettir
                    left += 1
                    right -= 1
                elif total < 0:
                    left += 1  # Toplam negatifse, toplamı artırmak için sol işaretçiyi hareket ettir
                else:
                    right -= 1  # Toplam pozitifse, toplamı azaltmak için sağ işaretçiyi hareket ettir
        return result

        
        

Complexity

• Time complexity (Zaman Karmaşıklığı): O(n^2), burada n dizinin uzunluğudur. Dizi sıralandıktan sonra, her eleman için O(n) karmaşıklığında bir iki işaretçi arama yapılır.
• Space complexity (Alan Karmaşıklığı): O(1) ya da O(n), çözüm setini saklamak dışında ekstra bir alan kullanılmaz.