for i in xrange(len(int)):
  if (s - int[i]) in int[i+1::]:

For every i you have to check from i+1th element to the last element. That seems O(n^2) to me.

You should look at the second index that completes the pair. Whichever pair has "earlier" closing index should be the answer.

In this case, the second index of (3, 7) is 4, which comes before 5, the second index of (5, 5).

Can someone give more hints on memoization? Still can't figure out how to beat the long list test.