Amazon Software Development Engineer interview questions

Given a random array with integers, find every pair that sum up to a certain number. It is a bit hard to understand the interviewer's accent. He sent me a link so that I could write code online. Talked about what I think about this program then wrote code. First I gave the O(n^2) solution, then I gave the O(nlogn) solution, but he looked for a O(n) solution.