Pular para o conteúdo

Pares abaixo do orçamento

Fácil#sorting#two-pointers~20 min

A missão

Problema

Uma loja lista os preços dos itens, e um preço pode até ser negativo depois de um reembolso. Conte os pares de dois itens diferentes cujos preços somam estritamente menos que um orçamento. Dois itens em posições diferentes formam um par à parte, mesmo que os preços sejam iguais.

Exemplos

Input:  prices = [4, -2, 0, 3, 1], budget = 3
Output: 5
Por quê: (4, -2), (-2, 0), (-2, 3), (-2, 1) e (0, 1) somam menos de 3
Input:  prices = [2, 2, 2], budget = 5
Output: 3
Por quê: cada uma das três formas de escolher dois dos valores 2 soma 4
Input:  prices = [5], budget = 100
Output: 0
Por quê: edge case: um item sozinho não forma par

Dicas

0 / 3

Tempo-alvo
O(n log n)
Espaço-alvo
O(n)

Restrições

  • prices are integers and can be negative

Travou na ideia, e não no código? O(n²) e loops aninhados explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado