İçeriğe geç

Bütçenin altındaki çiftler

Kolay#sorting#two-pointers~20 dk

Görev tanımı

Problem

Bir mağaza ürün fiyatlarını listeliyor ve bir fiyat iadeden sonra negatif bile olabiliyor. Fiyatlarının toplamı bütçeden küçük (eşitse sayılmaz) olan iki farklı ürünün çiftlerini say. Farklı konumlardaki iki ürün, fiyatları eşit olsa bile ayrı bir çift oluşturur.

Örnekler

Input:  prices = [4, -2, 0, 3, 1], budget = 3
Output: 5
Neden: (4, -2), (-2, 0), (-2, 3), (-2, 1) ve (0, 1)'in hepsinin toplamı 3'ten küçük
Input:  prices = [2, 2, 2], budget = 5
Output: 3
Neden: 2'lerden ikisini seçmenin üç yolunun her biri 4 eder
Input:  prices = [5], budget = 100
Output: 0
Neden: edge case: tek ürün çift oluşturamaz

İpuçları

0 / 3

Hedef zaman
O(n log n)
Hedef alan
O(n)

Kısıtlar

  • prices are integers and can be negative

Kodda değil de fikirde mi takıldın? O(n²) ve iç içe döngüler bunu anlatıyor.

Python 3Ctrl+Enter çalıştırır
Özel test case