Bir Kuralı Karşılayan Pencereleri Sayma

Bazen en uzun alt diziyi bulmak değil, bir kuralı sağlayan alt dizileri saymak gerekir. Küçük bir yöntem bunu kolay bir kaydırmalı pencere problemine dönüştürür. 🔢

Bir şeyden tam olarak K tane içeren alt dizileri doğrudan saymak zordur. Sınır sürekli değiştiğinden tek ve temiz bir pencere oluşturmak kolay değildir.

En fazla K içeren alt dizileri tek bir pencereyle saymak çok daha kolaydır. Sağı genişletirken, her geçerli sol konum bir alt dizi oluşturur.

Tam K, atMost(K) eksi atMost(K - 1) değerine eşittir. İki kolay sayımı birleştirerek aslında istediğiniz zor sayımı elde edersiniz.

En fazla k içeren alt dizileri sayan tek bir işlev yazın. Bu işlev bir pencereyi kaydırır ve sayı k'yı aştığında pencereyi küçültür.

Sağı genişletin ve pencereyi güncelleyin. Pencere k'dan fazla değer içerdiği sürece solu ileri taşıyarak tekrar aralığa sokun.

Pencereyi düzelttikten sonra, sağda biten ve başlangıcı soldan itibaren herhangi bir konum olan her alt dizi geçerlidir. Sağ eksi sol artı bir değerini ekleyin.

Sabit bir sağ konumu için geçerli başlangıçlar sol, sol+1 ve sağa kadar olan konumlardır. Bu, tamamı en fazla k koşulunu sağlayan tam olarak right - left + 1 alt dizi demektir.

Yardımcı işlevi iki kez çalıştırın ve sonuçları çıkarın. Her çağrı O(n) sürdüğünden, tam K sayımı da genel olarak doğrusal kalır.

k sıfırken atMost(k - 1) ifadesi eksi bir kullanır. Yardımcı işlevin yine anlamlı bir sıfır sayımı döndürmesi için bu durumu ele alın.

Bu en fazla eksi en fazla fikri, tam olarak K farklı değer, K tek sayı veya pencere başına tekdüze herhangi bir özellik içeren alt dizileri saymaya uygundur.

Tam K sayımı yalnızca atMost(K) eksi atMost(K - 1) değeridir. Her yardımcı işlev bir pencereyi O(n) sürede kaydırır; böylece toplam sayım doğrusal kalır. ✅