I was asked a question for a job interview and I did not know the correct answer....

The question was:

If you have an array of 10 000 000 ints between 1 and 100, determine (efficiently) how many pairs of these ints sum up to 150 or less.

I don't know how to do this without a loop within a loop, but that is not very efficient. 

Does anyone please have some pointers for me?