While many answers have been given above, every one of them is a quadratic-time solution

Great solution, but throop's hash solution is linear like yours.