Toplamı sıfır olan üçlüler

Problem

Bir tamsayı dizisi veriliyor. Dizinin farklı üç konumundaki elemanlardan toplamı 0 olan tüm üçlüleri bul. Sonuçta değer olarak aynı olan üçlü birden fazla kez yer almamalı: [-1, 0, 1] bir kez listelenir, dizide kaç tane -1 olduğundan bağımsız olarak. Üçlülerin ve üçlü içindeki sayıların sırası önemli değil.

Girdi:  [2, -3, 0, 1, -1, 1, -2]
Çıktı:  [[-3, 1, 2], [-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]

Girdi:  [0, 0, 0, 0]
Çıktı:  [[0, 0, 0]]

Netleştirme soruları

• Sonuçta değer olarak aynı üçlüler tekrar edebilir mi? (Hayır; bu, problemin asıl zorluğu.)
• Index mi değer mi döndürmeliyim? (Değer; bu sayede sıralama serbest.)
• Girdiyi değiştirebilir miyim (yerinde sıralama)?
• Dizi boyutu ne? (3.000'e kadar; O(n²) kabul, O(n³) değil.)
• Hedef her zaman 0 mı, yoksa genel bir target mı?

İpuçları

Yaklaşım

Brute force: Üç iç içe döngüyle tüm üçlüleri dene, sıralanmış halini bir Set<List<Integer>>'e at. O(n³) zaman; n = 3.000 için 4,5×10⁹ işlem. Tekrarları set ile temizlemek de ek maliyet.

Hash map'li Two Sum ile: Her i için kalan elemanlarda hash set ile çift ara. O(n²) zaman ama tekrar yönetimi karmaşık ve O(n) ek bellek gerekir.

Optimal, sırala + iki işaretçi: Diziyi sırala (O(n log n)). Her i için left = i+1, right = n-1 ile başla:

• Toplam negatifse daha büyük bir değer gerekir: left++.
• Pozitifse daha küçük: right--.
• Sıfırsa üçlüyü kaydet ve iki işaretçiyi de içeri al.

Neden doğru: sıralı dizide left'i artırmak toplamı artırır ya da aynı bırakır, right'ı azaltmak azaltır. Bir işaretçiyi hareket ettirdiğimizde elediğimiz çiftlerin hiçbiri çözüm olamaz (ör. toplam negatifken nums[left], mevcut right ile bile yetmiyorsa daha küçük right'larla hiç yetmez).

Tekrar yönetimi sorunun kalbidir:

1. i > 0 && nums[i] == nums[i-1] ise i'yi atla; aynı ilk elemanla aynı üçlüler tekrar bulunurdu.
2. Üçlü bulunduktan sonra left'i aynı değerleri geçene kadar ilerlet. right için ayrıca atlama gerekmez: left yeni bir değere geçtiğinde, aynı right değeriyle toplam artık 0 olamaz ve döngü right'ı kendiliğinden azaltır.

Ek optimizasyon: sıralı dizide nums[i] > 0 ise sağındaki her şey de pozitiftir, toplam 0 olamaz; döngü kırılır.

Java çözümü

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public final class ThreeSum {

    public List<List<Integer>> threeSum(int[] nums) {
        int[] sorted = nums.clone();                               // girdiyi değiştirme
        Arrays.sort(sorted);
        List<List<Integer>> triplets = new ArrayList<>();
        for (int i = 0; i < sorted.length - 2; i++) {
            if (sorted[i] > 0) {
                break;                                             // en küçük pozitifse toplam 0 olamaz
            }
            if (i > 0 && sorted[i] == sorted[i - 1]) {
                continue;                                          // aynı ilk eleman = aynı üçlüler
            }
            int left = i + 1, right = sorted.length - 1;
            while (left < right) {
                int sum = sorted[i] + sorted[left] + sorted[right];
                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                    triplets.add(List.of(sorted[i], sorted[left], sorted[right]));
                    left++;
                    right--;
                    while (left < right && sorted[left] == sorted[left - 1]) {
                        left++;                                    // ikinci elemanın tekrarlarını atla
                    }
                }
            }
        }
        return triplets;
    }
}

Girdiyi clone() ile kopyalayıp sıraladım; çağıranın dizisini değiştirmek yan etkidir. Mülakatta "yerinde sıralayabilir miyim?" diye sormak ve cevaba göre davranmak beklenir.

Karmaşıklık

• Zaman: O(n²). Sıralama O(n log n); dış döngü n, her i için iki işaretçi taraması O(n).
• Bellek: O(n) kopya için (yerinde sıralamada Arrays.sort primitive dizide dual-pivot quicksort kullanır, O(log n) yığın). Sonuç listesi hariç.
• Alt sınır notu: 3Sum'ın genel olarak O(n²)'den belirgin biçimde hızlı çözülemeyeceği varsayılır (3SUM-hardness); mülakatta "daha iyisi var mı?" sorusuna "bilinen pratik bir yöntem yok" demek doğrudur.

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı; 3.000 rastgele girdide (değerler -5..5, tekrar yoğun) O(n³) set'li brute force ile karşılaştırıldı ve her çıktıda tekrar eden üçlü olmadığı ayrıca kontrol edildi.

Mülakatçı için

Bu soru adayın bir problemi bildiği bir probleme indirgeyip indirgeyemediğini (Two Sum) ve tekrar yönetimini sistematik yapıp yapmadığını ölçer. Set ile tekrarları sonradan temizlemek çalışır ama hem yavaş hem de "problemi kontrol altına almamak" sinyalidir; kabul et ama nedenini sor.

İpucu zamanlaması: Aday O(n³)'te kalırsa "bir elemanı sabitlersen geriye ne kalır?" de. Sıralama fikrine ulaşamazsa ikinci ipucunu ver. Tekrar hatası yaparsa [0, 0, 0, 0] ve [-1, -1, 2, 2, -1] girdilerini kodla yürütmesini iste. right için de atlama döngüsü yazması hata değildir; neden gerekmediğini açıklayabiliyorsa artı puan.

Takip soruları:

1. 4Sum ya da genel kSum? (Beklenen: k-2 seviye sabitleme + iki işaretçi, O(n^(k-1)); rekürsif kSum; toplamlarda long ile taşma koruması.)
2. Üçlüleri değil, sadece sayısını isteseydim (index'e göre, tekrarlar dahil)? (Beklenen: sıralı dizide eşit değer bloklarını kombinasyonla saymak.)
3. Hedefe en yakın toplam? (Beklenen: aynı iskelet, fark minimizasyonu; LeetCode 16.)

Benzer problemler

• Two Sum (LeetCode 1) ve Two Sum II (LeetCode 167) (bu sette: two-sum).
• 3Sum Closest (LeetCode 16).
• 4Sum (LeetCode 18).
• 3Sum Smaller (LeetCode 259).
• Container With Most Water (LeetCode 11): iki uçtan işaretçi (bu sette: container-with-most-water).